This happens because another fingerprint is associated with the remote machine IP.Man in the middle warning.
For all examples below just replace the value after -R with your device:
ssh-keygen -R server-name
ssh-keygen -R server.ip.addre.ss
ssh-keygen -R 192.168.1.25
ssh-keygen -R server1.example.com