So, BitBucket has had some of their hostkeys have been leaked, so they are moving to new keys. This is all fine, but my current ssh setup wasn't using the new algorithms, as I could see when running ssh git@bitbucket.org host_key_info The output was telling me