Gitolite - remote: FATAL: fingerprinting failed for 'keydir/'

I just hit this problem while working on a new install. There was a change to the key fingerprint format in OpenSSH at version 6.8:

Add FingerprintHash option to ssh(1) and sshd(8), and equivalent command-line flags to the other tools to control algorithm used for key fingerprints. The default changes from MD5 to SHA256 and format from hex to base64.

Fingerprints now have the hash algorithm prepended. An example of the new format: SHA256:mVPwvezndPv/ARoIadVY98vAC0g+P/5633yTC4d/wXE Please note that visual host keys will also be different.

The latest git checkout of gitolite is aware, since 18th March '15, of this new format.

As I documented in "Getting fatal: object is corrupted when pushing to a remote repo", this is due to an incorrect ssh key.

I like to generate my private/public keys like so (not password protected):

ssh-keygen -t rsa -f "$HOME/.ssh/git" -C "Gitolite access (not interactive)" -q -P ""