On Debian, I can generate new SSH server keys:
rm /etc/ssh/ssh_host_*
dpkg-reconfigure openssh-server
but that will generate the keys with default values, ie 2048 RSA key.
What is happening under the hood, when I execute dpkg-reconfigure openssh-server ?
How can I change these defaults (ie, rsa to 4096), when generateing new server keys ?
Run this (as root) instead:
#!/bin/sh
# clean up old keys or complain you're not root
cd /etc/ssh && rm ssh_host_*key* || echo "Run this as root!" >&2 && exit 2
# generate; see https://stribika.github.io/2015/01/04/secure-secure-shell.html
ssh-keygen -t ed25519 -f ssh_host_ed25519_key -N "" < /dev/null
ssh-keygen -t rsa -b 4096 -f ssh_host_rsa_key -N "" < /dev/null
# zero for untrusted keys (prevents their recreation with dpkg-reconfigure)
touch ssh_host_dsa_key ssh_host_ecdsa_key
# restart ssh
service ssh restart
I disabled DSA (which is highly insecure) and ECDSA (which has less worrisome risks, see prior link or Secure Secure Shell).
dpkg-reconfigure will not touch your pre-existing keys (I see you recognized this, that's why you ran rm first). In fact, it's not even necessary to reconfigure; a simple service ssh restart should suffice.
If do this manually, you can preserve your existing ed25519 key; the defaults are good for it.
All clients' ~/.ssh/known_hosts files for this host will now all be wrong. You can just replace the matching entry after the first space with the new .pub file or re-verify the signatures. I do that with ssh localhost on the server (and I always say "no") to get the hash, but the "right" way to do it is:
ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub
The following command will generate a 4096-bit RSA keypair:
ssh-keygen -t rsa -b 4096
See then man page for ssh-keygen for more info.
