If you are downloading an Linux Image for i.e. Embedded Systems like Raspberry Pi, sometimes, the SSH Keys are still on the system and are not recreated.
To do that manually, just enter:
sudo rm /etc/ssh/ssh_host_*
sudo dpkg-reconfigure openssh-server
sudo service ssh restart