Run this (as root) instead:
# 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.
~/.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