Fedora and CentOS automatically regenerate SSH host keys on bootup if the key files are missing. This makes it easy to trigger regeneration as you simply remove the keys, and reboot the server. Other distributions are not quite as forgiving and require manual intervention. These are the steps I've used on Debian to get updated host keys.

rm /etc/ssh/ssh_host_*
ssh-keygen -f /etc/ssh/ssh_host_rsa_key     -N '' -q -t rsa
ssh-keygen -f /etc/ssh/ssh_host_ecdsa_key   -N '' -q -t ecdsa
ssh-keygen -f /etc/ssh/ssh_host_ed25519_key -N '' -q -t ed25519

ls /etc/ssh/*key* -lsh

systemctl restart sshd

Debian 9 ships with these versions of some core packages:

Debian 8 has been released and I gathered the versions of some core packages: