I’m a big fan of virtualization. I find it very useful both on my workstation as for the servers. What this means is that I often clone virtual machines to repurpose, run tests or simply add web capacity for load balanced sites. One of the steps is that you have to regenerate the ssh keys (besides the usual suspects that are changing IP, hostname and so on) so you don’t have multiple hosts with the same ssh keys. At least on CentOS and RHEL this simply means removing all the keys from /etc/ssh
The init script for SSH will detect that the host keys are missing and will regenerate them. Comment below if this works for other distros!