No Debian, a regeneração de chaves do host pode acontecer com:
rm /etc/ssh/ssh_host_*
dpkg-reconfigure openssh-server
Em distribuições baseadas em RedHat você pode definir o tipo de chaves privadas e públicas do servidor que o script init criará automaticamente, com a variável AUTOCREATE_SERVER_KEYS variable.
Você pode fazer isso no Debian e, se sim, como?