I had the same issues I had done like this to solve out my problem.
here is the Solution ::
Solution : Add correct host key in /home/user/.ssh/known_hosts
It is not necessary to delete the entire known_hosts file, just the offending line in that file. For example if you have 3 server as follows.
myserver1.com,64.2.5.111 ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAIEA11FV0EnGahT2EK8qElocjuHTsu1jaCfxkyIgBTlxlrOIRchb2pw8IzJLOs2bcuYYfa8nSXGEcWyaFD1ifUjfHelj94AAAAB3NzaC1yc2EAAAABIwAAAIEA11FV0E
nGahT2EK8qElocjuHTsu1jaCfxkyIgBTlxlrOIRchb2pw8IzJLOs2bcuYYfa8nSXGEcWyaFD1ifUjfHelj94H+uv304/ZDz6xZb9ZWsdm+264qReImZzruAKxnwTo4dcHkgKXKHeefnBKyEvvp/2ExMV9WT5DVe1viVwk=
myserver2.com,125.1.12.5 ssh-rsa
AAAAB3NzaC1yc2EAAAABIwAAAQEAtDiERucsZzJGx/1kUNIOYhJbczbZHN2Z1gCnTjvO/0mO2R6KiQUP4hOdLppIUc9GNvlp1kGc3w7B9tREH6kghXFiBjrIn6VzUO4uwrnsMbnAnscD5EktgI7fG4ZcNUP 5+J7sa3o+rtmOuiFxCA690DXUJ8nX8yDHaJfzMUTKTGxQz4M/H2P8L2R//qLj5s3ofzNmgSM9lSEhZL/IyI4NxHhhpltYZKW/Qz4M/H2P8L2R//qLj5s3ofzNmgSM9lSEhZL/M7L0vKeTObue1SgAsXADtK3162a/Z6MGnAazIviHBldxtGrFwvEnk82+GznkO3IBZt5vOK2heBnqQBfw=
myserver3.com,125.2.1.15 ssh-rsa
5+J7sa3o+rtmOuiFxCA690DXUJ8nX8yDHaJfzMUTKTGx0lVkphVsvYD5hJzm0eKHv+oUXRT9v+QMIL+um/IyI4NxHhhpltYZKW
as3533dka//sd33433////44632Z6MGnAazIviHBldxtGrFwvEnk82/Qz4M/H2P8L2R//qLj5s3ofzNmgSM9lSEhZL/M7L0vKeTObue1SgAsXADtK3162a/Z6MGnAazIviHBldxtGrFwvEnk82+GznkO3IBZt5vOK2heBnqQBfw==
To delete 2nd server (myserver.com), open file:
# vi +2 .ssh/known_hosts
And hit dd command to delete line. Save and close the file. Or use following
$ vi ~/.ssh/known_hosts
Now go to line # 2, type the following command
:2
Now delete line with dd and exit:
dd
:wq
Check out this full video Tutorial based on your problem:
SSH Host Key Change Error