SSH keys regenerated on first reboot after enabling SSH
When first enabling SSH, host keys are generated, and the generation is shown in /var/log/messages (but not on console).
However, upon the subsequent reboot, SSH host keys are again generated, which gets logged on the console only (but not in /var/log/messages). From then on, this second set of keys persists across reboots.
At any given point in time, the current SSH host keys can be checked either by connecting via SSH or by "ssh-keygen -l -f /etc/ssh/ssh_host_rsa_key.pub" (for the RSA key). Prior to reboot, it shows the first set of keys. After reboot, it shows the second.
If you happen to be unfortunate enough to confirm your host keys on your admin clients before that first reboot, you'll be very surprised when you next try to SSH and are warned that the host keys have changed, with no mention of the change in the server's log files...
2) Enable SSH
3) Check the SSH keys (/var/log/messages, ssh-keygen or ssh)
4) Reboot and watch the console after ntpd is started, you'll briefly see the keys being regenerated
5) Confirm the new SSH keys (ssh-keygen or ssh)
6) Reboot, no SSH keys are generate when starting sshd.
7) Confirm the new SSH keys have persisted