You should trust the default options of
ssh-keygen and not try to fiddle with random sources and so on. These are delicate matters. You can rely on the OpenSSH developers for having done things correctly -- you can rely because you already rely on them for having done a proper, leak-free implementation of the OpenSSH protocol, something which is far from easy.
For RSA, DSA, ElGamal, Diffie-Hellman, and similar algorithms, 2048-bit keys are enough. Estimating the strength of such algorithms in a meaningful way is not easy, because the best known attack algorithms rely on an awful lot of raw CPU power but also memory, storage, data bandwidth, and applicability of parallel computing of linear algebra on huge spare matrices. So such estimates must guess how future computing architectures and envisioned specialized circuits will fare against a number of more-or-less orthogonal scales, and the whole thing is more about divination than scientific prediction. Nevertheless, some have tried to establish guidelines, see this site for a compendium of existing rulesets that have been published. For instance, NIST states that 2048-bit RSA or DSA keys are fine until at least year 2030; note that the same NIST says that 1024-bit RSA keys should not be used beyond 2010, and yet we are now in 2012 and nobody still knows how to actually crack a 1024-bit RSA key (current record is for a 768-bit RSA key).
You are right in protecting your private key storage. This does not necessarily calls for a passphrase, though: in some contexts, the private key may reside in a desktop systems which is physically protected, and that could be deemed secure enough. Yet, strong passphrases are a nice reflex to have, and I can only encourage them.
As for key renewal, I would rather advise against it. Key renewal is a relatively complex operation because you have to transport the public keys to all relevant places (the
.ssh/authorized_keys on the servers to which you want to connect); if you forget one, then you will have to engage in a recovery procedure later on, and recovery procedures are, by definition, breaches of security. Controlled breaches, but breaches nonetheless. So you should renew your key only insofar as it helps you sleep at night, but key renewal is likely to be overdone. Remember that if an attacker can obtain your private key once, then he can plant his own public key in all the servers himself: changing your key will not stop him. So key renewal has relatively little impact on security anyway.