SSH: The authenticity of host <host> can't be established

It's telling you that you've never connected to this server before. If you were expecting that, it's perfectly normal. If you're paranoid, verify the checksum/fingerprint of the key using an alternate channel. (But note that someone who can redirect your ssh connection can also redirect a web browser session.)

If you've connected to this server before from this install of ssh, then either the server has been reconfigured with a new key, or someone is spoofing the server's identity. Due to the seriousness of a man-in-the-middle attack, it's warning you about the possibility.

Either way, you have a secure encrypted channel to somebody. No one without the private key corresponding to fingerprint 97:8c:1b:f2:6f:14:6b:5c:3b:ec:aa:46:46:74:7c:40 can decode what you send.

The key you use to authenticate yourself is unrelated... you wouldn't want to send authentication information to a fraudulent server who might steal it, and so you should not expect any changes depending on whether you're going to use a passphrase or private key to login. You simply haven't gotten that far in the process yet.

Let us say you meet someone to exchange some business secrets. Your advisor tells you that you have never meet that person before, and that it can be an impostor. Furthermore, for the next meetings with him, your advisor is not going to warn you anymore. That is what the message means. The person is the remote server, and your advisor is the ssh client.

I don't think it is paranoid to double-check the identity of the person before sharing secrets with her. For instance you could open a web page with a picture of her and compare it with the face in front of you. Or check her identity card.

For the bitbucket server, you could use a different, more trusted computer and get the picture of its face from it, and then compare it with the one you get in the computer you are using now. Use:

 ssh-keyscan -t rsa bitbucket.org | ssh-keygen -lv -f -

If the faces match, you can add the key to the file e.g. ~/.ssh/known_hosts (standard location in many Linux distributions) with:

ssh-keyscan -t rsa -H bitbucket.org >> ~/.ssh/known_hosts

and the ssh client will not warn you as it already knows her face. It will compare the faces anytime you connect. That is very important. In the case of an impostor (e.g. a man-in-the-middle attack), the ssh client will reject the connection because the face will have changed.

I simply had to create the known_hosts text file in ~/.ssh

sudo vim ~/.ssh/known_hosts
sudo chmod 777 ~/.ssh/known_hosts

After doing this, it added the host and I never saw the message again.