Error `could not load host key` when trying to recreate SSH host keys

None of the answers above worked for me. I fixed my ubuntu system by doing the following:

/usr/bin/ssh-keygen -A

sudo ssh-keygen -f /etc/ssh/ssh_host_rsa_key -N 'myverylongpasswordhere' -b 4096 -t rsa

recreates me the keys. but, after restarting the server, i recieve

could not load host key: /etc/ssh/ssh_host_rsa_key

You create a hostkey with a password. Is there any customization to unlock that hostkey? If not, then I think that is what is to be expected: the script that manages the service starts up, tries to load the hostkey, and fails. As far as I know you shouldn't create hostkeys protected with passwords.

If you are interested in hardening your SSH server then I recommend reading https://stribika.github.io/2015/01/04/secure-secure-shell.html the command used to create the hostkey in that document is:

ssh-keygen -t rsa -b 4096 -f ssh_host_rsa_key

But you should read the entire document before making any changes.