[ Thanks to GeekRide
for this link. ]
“A. The possible reasons for getting this error are:
* You have re-installed you system and trying to ssh to the
newly installed system.
* You have assigned the IP address of one system to another system
and trying to ssh.
* You system is dual boot with different ssh keys in both flavors
of linux.
* You are using an IP for load balancing and trying to ssh to the
same IP.
* You generated new ssh keys for your system. (Read this article
for the re-generation of the host keys: Generate SSH host keys)
* Someone trying to do some nasty things”