Ubuntu, how to regenerate OpenSSH host keys

First, change directory to /etc/ssh

cd /etc/ssh

now, remove the old rsa and dsa keys files

sudo rm ssh_host_*

Generate new keys

sudo dpkg-reconfigure openssh-server

If you wanto to be 100% sure that the server you are connecting to is the one it claims to be, take note of the RSA and DSA fingerprint

sudo ssh-keygen -l -f ssh_host_rsa_key
sudo ssh-keygen -l -f ssh_host_dsa_key

to check against the fingerprint displayed next time you are going to connect.

Last, update your known_hosts file

~/.ssh/known_hosts

removing the line that contains the old reference, otherwise you'll get the following message

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!