If you need to regenerate your SSH Host Keys do the following.

1. delete your old keys

rm /etc/ssh/ssh_host_*

2. reconfigure the ssh server

dpkg-reconfigure openssh-server

That’s it now you can update you known_hosts file when you connect next time. If you use strict checking which you should you will need to delete the key from you known_hosts file in you home directory. Or you will not be able to connect.