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.