I've been using a 1024-bit RSA key for passwordless SSH between my own systems for years. More recently I've also started using it for passwordless access to my hosting providers and to source code repositories.
Is using the same key pair for an extended period of time, and to access multiple resources, an issue?
I'm going to take a different position from others here. My recommendation: There's no need to change your SSH private key, unless you have a good reason to change it.
Rationale: Crypto doesn't wear out. It doesn't become weaker with repeated use.
The biggest reason to change your private key is if you have a reason to suspect it has been compromised or is no longer secure. For instance, if one of your machines is hacked, and you have a copy of your private key stored on that machine, I'd recommend changing your SSH key. Similarly, if one of your backups goes walkabout, and it had a copy of your SSH private key on it, I'd recommend changing your SSH key. Or, if you generated your private key on an old Debian system, then it may be insecure and I'd recommend changing it. However, if you don't have a reason like that to suspect that your private key is compromised, I see no need to change it.
The downside of changing your key unnecessarily is now you have to update the authorized_keys file on every machine you might ever log into. That's a bit tedious.
I suspect the reason that some folks are recommending you change your private key is for prophylactic reasons: what if one of the machines storing your private key got hacked, and you were unaware, and now the hacker no longer has access? The hacker may still have your private key. Therefore, there may be some value to occasionally changing your SSH private key, to limit the exposure in that kind of scenario. But personally, I suspect that kind of scenario is very rare and probably not worth the trouble of changing your SSH key. So, if others prefer to change their SSH keys periodically, I can understand their reasons -- but personally, I wouldn't bother.
P.S. If we were talking about a host key (rather than your personal key), then there is an even stronger reason not to unnecessarily change the host key: if you change the host key, everyone who tries to log into that machine will start getting warnings that they might be under attack. If people routinely see these warnings, they'll start to treat them as meaningless noise (it'll be a boy-cried-wolf situation), undermining their value. So, don't routinely change host keys without good reason.
Yes, strictly speaking it is recommended to expire SSH keys after a while (this could depend of the key length, vulnerabilities found in the key generator, etc.). However such mechanism was not foreseen by SSH. And it is cumbersome to go to every possible remote hosts and delete the public key.
There is a solution - though I never tried it yet, but keep it for when I will have some free time - MonkeySphere for OpenSSH project. It will allow to manage expiration of your keys as far as I understood it!
Well, of course it depends on the sensitivity of your data: you're protecting your data from your neighborhood, from business attacks, from government ?
This article estimates that is possible to build a computer that can break RSA keys, 1024 bits, in a year, spending some millions. They mention lots of studies, all recomending at least 2048 bits.
This site can help you estimating how long will your key resist to attacks.
And this question gives a lot of answers about the keysize.
Also, remember that using your private key correctly doesn't mean you'll have problems if you have more that one host holding your public key, nor the times you use it will make it weaker. That's why private-public keys were created: to be used without increasing risks as they were more used.
As far as I know, there is no "key-wear" with RSA keys, so there's no problem keeping the same set of keys. If you suspect your keys might have been compromised, you can generate new keys, but otherwise it isn't really necessary.
It is your trust of remote server, if you don't trust remote server, then changing your ssh key (new private key) and uploading new public part to a remote server has no benefit.
Your private ssh key doesn't travel over network... Security of your private ssh keys is your responsability.
If you question was more general, it means how to revalidate keys of users, then it depends. You can use some tools like cfengine, puppet to upload users' public ssh keys to their homedirs regularly from a repository/DB which would hold a timestamp. Then you can send mail to user to revalidate the usage of the key, or to his manager. Or you can use certificates with ssh. Although OpenSSH team hasn't developed any info about expiring certificates...
Be far from various hacked openssh solutions and their patches. Would they support it in the future?
