sudo ssh-keygen -f /etc/ssh/ssh_host_rsa_key -N 'myverylongpasswordhere' -b 4096 -t rsa
recria-me as chaves. mas, depois de reiniciar o servidor, eu recebo
could not load host key: /etc/ssh/ssh_host_rsa_key
Você cria um hostkey com uma senha. Existe alguma personalização para desbloquear esse hostkey? Se não, então eu acho que é o que é esperado: o script que gerencia o serviço é iniciado, tenta carregar o hostkey e falha. Tanto quanto eu sei que você não deve criar teclas de host protegidas com senhas.
Se você estiver interessado em proteger seu servidor SSH, recomendamos que leia o link o comando usado para criar o hostkey nesse documento é:
ssh-keygen -t rsa -b 4096 -f ssh_host_rsa_key
Mas você deve ler o documento inteiro antes de fazer qualquer alteração.