Public Key SSH doesn't match and is changing

I’ve created a public/private key pair according to the Ubuntu initialization tutorial and the public key is correctly set up. I create a new user and grant it administrator access and it uses the public key to login via ssh. Root user is prohibited in ssh login due to security concerns.

My problem is, sometimes I can successfully connect to the server by ssh user@ipaddress And sometimes when I do this it will tell me there “REMOTE HOST IDENTIFICATION HAS CHANGED!”, from which I found that the fingerprint is different from what it should be, so I need to delete the old key in “known_hosts” file and accept a new public key. If I continue by accept the new key, the ssh session will ask me to type the password of the user, while there’s no need to enter the password in normal case since I have the private key. And even if I fill in the correct password for the user, I still cannot log in.

More interestingly, sometimes I didn’t do anything to the problem and came back a few hours later and try to connect via ssh again, I will find that the fingerprint changed AGAIN! After accept the key, I can correctly login into the server!

So my problem is, why the fingerprint is changing? Am I under attack? Why it will ask me to enter the password while it is not supposed to ask for it?

Thank you!