Man cloned mehrere Maschinen mit einem vorhandenen Image und hat das Problem, dass alle Host-Keys gleich sind unter Debian.
Lösung: Im Image die /etc/ssh/ssh_host* Files löschen und neu generieren lassen im Init-Skript ala:
check_keys_avail() { if [ ! -e /etc/ssh/ssh_host_key_dsa ]; then dpkg-reconfigure openssh-server fi } case "$1" in start) check_privsep_dir check_keys_avail