BitBucket: Host key verification failed

The message says

Host key verification failed.

nothing about authentication, so you are working on the wrong field. It means that the host key of the bitbucket.org is not in your ~/.ssh/known_hosts and your client does not have any way how to verify it. It was answered many times how to workaround it, but how to do it properly?

There is section in the bitbucket manuals, describing how their public keys and fingerprint looks like. So:

1. Run ssh bitbucket.org

2. It will prompt you with one of the fingerprints:

   The authenticity of host 'bitbucket.org (104.192.143.3)' can't be established.
   RSA key fingerprint is SHA256:*****.
   Are you sure you want to continue connecting (yes/no)?
   

3. You verify the fingerprint in the prompt is the same as on the bitbucket website:

   SHA256:zzXQOXSRBEiUtuE8AikJYKwbHaxvSc0ojez9YXaGp1A bitbucket.org (RSA)
   

4. You write yes and press enter to verify the connection works.

Or just copy the public key from the bitbucket website directly in the ~/.ssh/known_hosts file

echo "bitbucket.org,104.192.143.1 ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAubiN81eDcafrgMeLzaFPsw2kNvEcqTKl/VqLat/MaB33pZy0y3rJZtnqwR2qOOvbwKZYKiEO1O6VqNEBxKvJJelCq0dTXWT5pbO2gDXC6h6QDXCaHo6pOHGPUy+YBaGQRGuSusMEASYiWunYN0vCAI8QaXnWMXNMdFP3jHAJH0eDsoiGnLPBlBp4TNm6rYI74nMzgz3B9IikW4WVK+dc8KZJZWYjAuORU3jc1c/NPskD2ASinf8v3xnfXeukU0sJ5N6m5E8VLjObPEO+mN2t/FZTMZLiFqPWc/ALSqnMnnhwrNi2rbfg/rd/IpL8Le3pSBne8+seeFVBoGqzHM9yXw==" >> ~/.ssh/known_hosts

if nothing from the above helps, please run ssh -vvv bitbucket.org and post the output to the edited question.

mkdir ~/.ssh
touch ~/.ssh/known_hosts
ssh-keyscan bitbucket.org >> ~/.ssh/known_hosts