I encounter these same problems every time I set up a fresh computer – which doesn’t happen that often, that’s why I don’t have the steps in my muscle memory.

I had written this down before, but somewhere else; and since this website should become my one-and-only, definitive knowledge base (for public stuff), I now put the latest updates here.

By the way: Most of this here assumes that you’re using Microsoft Windows and Powershell!

(1) Generate a SSH key pair with PuTTY

Use PuTTY’s PuTTYgen program to generate a new SSH key pair (a private and a public key) on your local computer:

1. Start PuTTYgen and choose the Type (e.g. RSA) and possibly the Number of bits: 2048 (for example):

   By the way: GitLab.com recommends ED25519; for that, select in PuTTYgen (v0.81) as the type of key to generate EdDSA:
   “For EdDSA, the only valid sizes are 255 bits (these keys are also known as Ed25519 and are commonly used)”

   

2. Click on the Generate button and move the mouse cursor over the blank area, until the progress bar is done:
   

   

3. Optionally type in a comment (description) for this key and finally enter and confirm a key phrase (a “password”).
   Then click on Save private key (to a *.ppk file; PuTTY’s proprietary file format).
   

   

   There is also Save public key (to a text file), but I don’t have good experiences with that, at least in relation with BitBucket (see next step); that’s why I usually skip it and load and copy the public key from the PPK file later, select it from there and copy-&-paste it:

   Either pick Edit with PuTTYGen from the file’s context menu:	… or simply Load the file from within PuTTYgen:

(2) Add the public SSH key to your account settings

(2.1) BitBucket.org

1. Log in to BitBucket.org and go to your “Personal Settings”
   (by clicking on your avatar in the lower left; or by clicking on the “Settings” cog symbol on the top navigation bar; or… – as websites go, this may have changed by now.)

2. Select Security → SSH keys → Add key…
   Gotcha: You’ll get an Invalid Key error if you copy the Public Key out of a saved text file.
   Fix: Get the public key directly from PuTTYgen (see above).

Additional infos: Provide Bitbucket Cloud with your public key.

(2.2) GitLab.com

1. Log in to GitLab.com and select your avatar on the left sidebar.
2. Select “Edit Profile”; select “SSH Keys” (left sidebar); select “Add new key”; etc.

Additional infos: Add an SSH key to your GitLab account

(3) Load private SSH keys automatically on each Windows start

Use PuTTY’s Pageant to load the private SSH key(s) automatically a the startup of Windows.

When the following steps are done, you’ll only need to enter the passphrase of the key(s) once when Windows boots, instead of each time that Git wants to communicate with the remote repo at BitBucket.org.

1. The Startup folder is no longer reachable via Start Menu/GUI since Windows 10.
   Therfore, use the Run… command (Win+R) instead and enter shell:startup
   (or open a file explorer and navigate to C:\Users\<User>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Startup)

2. In that folder, create a new shortcut that points to the “Pageant” executable: Right click: New → Shortcut
   Edit the properties of this shorcut:

   • Set the target to the path where “Pageant” is installed; and provide the path(s) to the PPK file(s) as its command-line argument (multiple filepaths are separated by space); example:
     Target: "C:\Program Files\PuTTY\pageant.exe" "C:\path\to\PrivateKey1.ppk" "C:\path\to\PrivateKey2.ppk"

   • Or, if multiple PPK files should be loaded from the same folder, this can be shortend; example:
     Target: "C:\Program Files\PuTTY\pageant.exe" PrivateKey1.ppk PrivateKey2.ppk
     Start in: C:\path\to\

(4) Fixing up

(4.1) Error when trying to clone a repository: Could not read from remote repository

> git clone git@bitbucket.org:saoe/REPO-X.git

Cloning into '<REPO-X>'...
git@bitbucket.org: Permission denied (publickey).
fatal: Could not read from remote repository.

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

Fix: Tell Git for Windows that it should use PuTTY’s plink.exe for SSH tunneling:
Set the environment variable GIT_SSH to where it can find plink.exe (the user context is fine):

> [Environment]::SetEnvironmentVariable("GIT_SSH", "C:\Program Files\PuTTY\plink.exe", "User")

(4.2) Error when trying to clone a repository: The host key is not cached for this server

> git clone git@bitbucket.org:saoe/REPO-X.git

The host key is not cached for this server:
  bitbucket.org (port 22)
You have no guarantee that the server is the computer you think it is.
[...]

Fix: You need to acquaint plink.exe with this host by calling it one time with that URL as its argument:

> &'C:\Program Files\PuTTY\plink.exe' bitbucket.org
> &'C:\Program Files\PuTTY\plink.exe' gitlab.com

Confirm with "Y" (store key in cache) and skip the following “Login as:” prompt by hitting the RETURN key.

After that, it should look like this (which is fine):

• BitBucket.org’s reply:

    Access granted. Press Return to begin session.
    Server refused to allocate pty authenticated via ssh key.
    You can use git to connect to Bitbucket. Shell access is disabled
  

• GitLab.com’s reply:

    FATAL ERROR: No supported authentication methods available (server sent: publickey)
  

Now you should be able to clone repos and commit & push changes to your remote repositories on BitBucket.org