SSH key changed got

When performing a push to my project on from IntelliJ, I got the following warning:

The server host key for the host has changed to 
b6:03:0e:39:97:9e:d0:e7:24:ce:a3:77:3e:01:42:09 (type ssh-rsa). 
Do you want to accept the changed key?

Trying a “git push” from the command line, I get the following error:

ssh_exchange_identification: Connection closed by remote host
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

There are some issues listed in the issue tracker for the latter, which was closed a week ago:

I can’t see a way of confirming the fingerprint to make sure that it is valid, so I don’t want to blindly accept a new key. Is anyone else seeing this problem, know how to resolve it, or know how to validate the key fingerprint?