How do I regenerate OpenSSH sshd server host keys stored in /etc/ssh/ssh_host_* files? Can I safely regenerate ssh host keys using remote ssh session as my existing ssh connections shouldn’t be interrupted on Debian or Ubuntu Linux? How do I regenerate new ssh server keys?

To regenerate keys you need to delete old files and reconfigure openssh-server. It is also safe to run following commands over remote ssh based session. Your existing session shouldn’t be interrupted.

Why regenerate new ssh server keys?

Most Linux and Unix distribution create ssh keys for you during the installation of the OpenSSH server package. But it may be useful to be able re-generate new server keys from time to time. For example, when you duplicate VM (KVM or container) which contains an installed ssh package and you need to use different keys from cloned machine.

Step # 1: Delete old ssh host keys

Login as the root and type the following command to delete files on your SSHD server:
# /bin/rm -v /etc/ssh/ssh_host_*
Sample outputs:

removed '/etc/ssh/ssh_host_dsa_key'
removed '/etc/ssh/ssh_host_dsa_key.pub'
removed '/etc/ssh/ssh_host_ecdsa_key'
removed '/etc/ssh/ssh_host_ecdsa_key.pub'
removed '/etc/ssh/ssh_host_ed25519_key'
removed '/etc/ssh/ssh_host_ed25519_key.pub'
removed '/etc/ssh/ssh_host_rsa_key'
removed '/etc/ssh/ssh_host_rsa_key.pub'

Step # 2: Reconfigure OpenSSH Server

Now create a new set of keys on your SSHD server, enter:
# dpkg-reconfigure openssh-server
Sample output:

Creating SSH2 RSA key; this may take some time ...
2048 SHA256:BLUkgjGdbcFX9wCsfOoIG4gtkdSeex4K/xcnsRo0qEA [email protected] (RSA)
Creating SSH2 DSA key; this may take some time ...
1024 SHA256:Ug9fJa14YMR9Fud/7bXTokffK/hM/sBVse10nSR/6Y8 [email protected] (DSA)
Creating SSH2 ECDSA key; this may take some time ...
256 SHA256:Rh6izWEXkCV6HZLIpzlGQje178vhDgb77ItaZgpDsIQ [email protected] (ECDSA)
Creating SSH2 ED25519 key; this may take some time ...
256 SHA256:UD4b7njwxWp1Q3wYf2R//udgPRzfGaeZ/6kE3VgZM+s [email protected] (ED25519)

You just regenerated new ssh server keys. You can restart ssh server:
$ sudo systemctl restart ssh
OR
$ /etc/init.d/ssh restart

Step # 3: Update all ssh client(s) known_hosts files

Finally, you need to update ~/.ssh/known_hosts files on client computers, otherwise everyone will see an error message that read as follows:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
f6:67:01:41:e6:20:06:4b:4b:fa:4b:c1:f1:45:45:e0.
Please contact your system administrator.
Add correct host key in /home/vivek/.ssh/known_hosts to get rid of this message.
Offending key in /home/vivek/.ssh/known_hosts:12
RSA host key for 202.54.xx.abc has changed and you have requested strict checking.
Host key verification failed.

Either remove host fingerprint or update the file using vi text editor (command must be typed on client machine):
$ ssh-keygen -R remote-server-name-here
Now login using ssh:
$ ssh [email protected]