Regenerate SSH host keys
This applies to OpenSSH installation on both Debian and Ubuntu.
Warning
Please note that while you could do issue the commands below over SSH maintaining the session, it is recommended to do this using the console. You could get yourself isolated from SSH if the connection gets dropped.
First, remove the existing host keys:
rm /etc/ssh/ssh_host_*
Then we reconfigure OpenSSH, which will trigger the keys to be regenerated:
dpkg-reconfigure openssh-server