In order to guard against a long-term cryptanalytic attack, every key must have an expiration date after which it is no longer valid (see Question 188.8.131.52). The time to expiration must therefore be much shorter than the expected time for cryptanalysis. That is, the key length must be long enough to make the chances of cryptanalysis before key expiration extremely small. The validity period for a key pair may also depend on the circumstances in which the key is used. The appropriate key size is determined by the validity period, together with the value of the information protected by the key and the estimated strength of an expected attacker. In a certificate (see Question 184.108.40.206), the expiration date of a key is typically the same as the expiration date of the certificate, though it need not be.
A signature verification program should check for expiration and should not accept a message signed with an expired key. This means that when one's own key expires, everything signed with it will no longer be considered valid. Of course, there will be cases in which it is important that a signed document be considered valid for a much longer period of time. Question 7.11 discusses digital timestamping as a way to achieve this.
After expiration, the old key should be destroyed to preserve the security of old messages (note, however, that an expired key may need to be retained for some period in order to decrypt messages that are still outstanding but encrypted before the key's expiration). At this point, the user should typically choose a new key, which should be longer than the old key to reflect both the performance increase of computer hardware and any recent improvements in factoring algorithms (see Question 220.127.116.11 for recent key length recommendations).
However, if a key is sufficiently long and has not been compromised, the user can continue to use the same key. In this case, the certifying authority would issue a new certificate for the same key, and all new signatures would point to the new certificate instead of the old. However, the fact that computer hardware continues to improve makes it prudent to replace expired keys with newer, longer keys every few years. Key replacement enables one to take advantage of any hardware improvements to increase the security of the cryptosystem. Faster hardware has the effect of increasing security, perhaps vastly, but only if key lengths are increased regularly (see Question 2.3.5).