After doing a yum update the other day I would get these warnings in /var/log/messages and when doing ssh into the host:
error: Could not load host key: /etc/ssh/ssh_host_key
To fix this, you need to be root and:
/usr/bin/ssh-keygen -A
service sshd restart