Several people have brought up the fact that ssh host keys are rarely rotated as an argument for not rotating ssl keys. That just seems like another problem to solve. (I apologize for a slightly off-topic answer, but several people here mentioned it so it seems appropriate)
See my answer above for why one might wish to rotate keys.
The following will be particularly useful for everyone who, for compliance reasons, is required to rotate ssh host keys, but who worries about the usability impact on end users.
1) Deploy an ssh_ca
(Remarkably complete instructions in man ssh-keygen)
ssh-keygen -f ssh_ca -b 4096
2) Distribute the certificate to your users: Add certificate authority line to ~/.ssh/known_hosts
@cert-authority *.domain.name ssh-rsa AAAAB3[...]== Comment
3) Sign your host keys (be sure to restrict each to an individual host)
ssh-keygen -s ssh_ca -I host.domain.name -h -n host.domain.name -V +52w /etc/ssh/ssh_host_rsa_key.pub
4) Configure server(s) to present certificate (/etc/ssh/sshd_config):
Any host key signed by the CA is now trusted by the client (no more blindly accepting a key sig the first time you connect)
Rolling the host key can now be done with no disruption to clients. The key signing can be rolled into the host build/orchestration process.
This is a good reference. This project created some useful tools around using ssh_ca for auto-expiring user access.