SSH warns that the host key / fingerprint has changed

A rebuilt instance (or a reused IP from a new spot instance) has a new host key, so this warning is expected. Remove the old entry and reconnect:

ssh-keygen -R INSTANCE-IP

If you see this on an instance you did not rebuild, confirm you're connecting to the correct, active IP before continuing.