What can cause a changed ssh fingerprint?

The correct assumption in this case is that you are connecting to a different server.

• Maybe a MitM attack or
• maybe your DNS is spoofed or
• maybe your data center has just removed your machine for a second because they got a call from the government and you are accidentally trying to connect to their "server unreachable" catchall machine or
• maybe your server has crashed under the sudden load and the aforementioned holds or ...

There are plenty of reasons you might be connecting to the wrong machine and you should definitely not proceed.

There are a couple of harmless reasons as well, false positives that make people sometimes connect anyway.

False positives I can think of right now:

• The server has removed an old ciphersuite which it doesn't want to support anymore.
• The server IP has changed and you have "CheckHostIP yes" in your config (default on many systems).
• You have connected to the same server using a different hostname (think about something like gitlab) since the default ciphersuites have changed. (This is really obscure but I have run into it.)
• The server has multiple SSH servers installed, and you're connecting to the same machine running a different SSH server (e.g., due to improperly configured startup behavior), which has its own separate keys.

Do note that as described here public key authentication prevents MitM attacks. It does of course not prevent you from simply logging into the wrong machine and then typing in your sudo password. So caution is still required.