Have your VM creation script call
ssh-keygen towards the end. From within the VM, the directory /etc/ssh/ will be used. Pre-existing SSH host keys have to be deleted, but be careful not to delete anything else.
Code:
ssh-keygen -a 17 -A
Again, don't run that inside your host, just inside the guest. If you have to run it from within the host, then mount the image and point to the relevant directory using the -f option:
Code:
ssh-keygen -a 17 -A -f /mnt
The -f would cause
ssh-keygen to put the new host keys in /mnt/etc/ssh/
See "man ssh-keygen" about the -A option.
Which distro is this for, including version?