Ok, eu sei porque isso acontece. Em /etc/rc.local é script:
#!/bin/sh
rm -f etc/ssh/ssh_host_*
/usr/bin/ssh-keygen -t rsa -N '' -f /etc/ssh/ssh_host_rsa_key
/usr/bin/ssh-keygen -t dsa -N '' -f /etc/ssh/ssh_host_dsa_key
/usr/bin/ssh-keygen -t rsa1 -N '' -f /etc/ssh/ssh_host_key
/usr/bin/ssh-keygen -t ecdsa -N '' -f /etc/ssh/ssh_host_ecdsa_key
/usr/bin/ssh-keygen -t ed25519 -N '' -f /etc/ssh/ssh_host_ed25519_key
systemctl restart ssh
DHCP6CCTLKEY=/etc/wide-dhcpv6/dhcp6cctlkey
# The key mustn\'t be world readable
umask 066
echo "Generating ${DHCP6CCTLKEY}..." >&2
dd if=/dev/random bs=32 count=1 2>/dev/null | uuencode -m ${DHCP6CCTLKEY} | head -n 2 | tail -n 1 > ${DHCP6CCTLKEY}
umask 022
mv -f /etc/rc.local.orig /etc/rc.local