The problem is that the version of Gitlab installed from those instructions (version 6.9.2) is too old (current version is 8.14) – ssh-keygen was then outputting MD5 based Fingerprint hashes; the default is now SHA256. The solution, as garnered from – Fixing gitlab’s “Fingerprint cannot be generated” error – is as follows:

• Edit <path-to-gitlab>/app/models/key.rb
• Change this line

cmd_output, cmd_status = popen(%W(ssh-keygen -lf #{file.path}), '/tmp')

• With this one

cmd_output, cmd_status = popen(%W(ssh-keygen -E md5 -lf #{file.path}), '/tmp')

• Restart Gitlab