Yes that could happen, but usually it doesn't happen frequently that CA certs are replaced because of security considerations.
Root certificates - the top level certificates - usually have a very long validity period. Replacing a root certificate is a out-of-band process. For instance, for browsers it means putting it into the default certificate store distributed within the browser installation. As they are commonly only used to create the CA certificates below them, they can be securely stored in a safe somewhere (all the more reason to use a secure, up to date browser). Even MD5 certificates may still be secure if the signed certificates are only created internally within the CA.
Of course it might be that certificates need to be replaced earlier than the "valid-to" date. For instance the signature or hash algorithms may need to be replaced or it is suspected that the key has leaked. For any other certificates than CA certificates the old certificates can be marked invalid in a CRL (Certificate Revocation List) or through OCSP (Online Certificate Status Protocol). CA certificates can be part of a chain that lead to the trusted root certificate; they do not have to be distributed with browsers, they can be received and verified during authentication.
As CA certificates may sign end user certificates (or other intermediate CA certificates) that are from a semi-trusted source there is a higher need to make sure that the signature algorithms supported by the certificate are secure. Of course CA certificates are more likely to be kept secure than end user certificates, so the (expected) loss of the private key should happen less often. If the security practices of the CA itself are sufficiently lacking there may not be any time to renew certificates, by the way.
So yes, CA certificates must be renewed from time to time, because there are security related issues or because they are near the date of expiry (usually there is some overlap between certificates validity period to allow everybody to switch).