This has been tried and tested on Fedora based distros. Forcing regeneration of host keys on Debian based distros may be different, you may need to use dpkg-reconfigure (dpkg-reconfigure openssh-server).

If you are having issues with SSH such as errors staring SSH service and the log or journald complains about SSH host keys you can regenerate them with ssh-keygen using the following command:

ssh-keygen -A

Passing the -A argument means for each of the key types (rsa1, rsa, dsa, ecdsa and ed25519) for which host keys do not exist, generate the host keys with the default key file path, an empty passphrase, default bits for the key type, and default comment. This is used by /etc/rc to generate new host keys.

If this does not work and you have access to the machines / server via console, VNC or even SSH and don't mind the risk of losing connection you can delete the old keys first with:

rm -rf /etc/ssh/ssh_host_*

Then regenerate with ssh-keygen again:

ssh-keygen -A