Um z.B. für ein Template bzw. golden image die SSH-Keys aus einer VM mit Debian/Ubuntu zu entfernen, reichen zwei simple Dinge:

/bin/rm -v /etc/ssh/ssh_host_

Damit werden die aktuellen SSH-Keys entfernt. Nun im Crontab (crontab -e) folgendes eintragen:

@reboot /usr/sbin/dpkg-reconfigure openssh-server; crontab -r

Damit wird dann beim nächsten Booten das Generieren der neuen Keys angestoßen, danach dann der crontab gelöscht.