Publickey authentication not working on OmniBus installation

Backstory: I’ve recently upgraded my GitLab instance from a Bitnami VM to a new VM running Ubuntu Server 16.04.
I migrated the DB using the standard backup/restore steps without issue. My repositories were on an nfs export, so the new instance was configured to look for repos on the mounted partition, and I rebuilt the hooks with gitlab-ctl.

The issue now is that publickey authentication is not working correctly. When the devs updated their remotes, and started hitting the server, they were asked for a password for the git user. To attempt to rectify this, we deleted the old ECDSA Host keys on the clients, went into gitlab web console and deleted old keys, re-generated keys (ssh-keygen), and re-created them on the gitlab web console. This worked for a few developers, but not for others.

What steps can I take to troubleshoot this issue? Are there log locations that would tell me more?

More info:

$ ssh -Tvvv git@my.gitlab.server

OpenSSH_7.3p1, LibreSSL 2.4.1
debug1: Reading configuration data /Users/me/.ssh/config
debug1: /Users/me/.ssh/config line 6: Applying options for my.gitlab.server
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 20: Applying options for *
debug2: resolving “my.gitlab.server” port 22
debug2: ssh_connect_direct: needpriv 0
debug1: Connecting to my.gitlab.server [::1] port 22.
debug1: Connection established.
debug1: identity file /Users/me/.ssh/gitlab_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/me/.ssh/gitlab_rsa-cert type -1
debug1: identity file /Users/me/.ssh/gitlab_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/me/.ssh/gitlab_rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.3
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.3
debug1: match: OpenSSH_7.3 pat OpenSSH* compat 0x04000000
debug2: fd 5 setting O_NONBLOCK
debug1: Authenticating to gitlab.monadnock.org:22 as ‘git’
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: local client KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1,ext-info-c
debug2: host key algorithms: ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc,3des-cbc
debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc,3des-cbc
debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,zlib@openssh.com,zlib
debug2: compression stoc: none,zlib@openssh.com,zlib
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1
debug2: host key algorithms: ssh-rsa,rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519
debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com
debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com
debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,zlib@openssh.com
debug2: compression stoc: none,zlib@openssh.com
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug1: kex: algorithm: curve25519-sha256@libssh.org
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:J28DWjZwzbs6nlIXG6NpeJpVqVLc4YVmauNwKbPcv+A
debug1: Host ‘gitlab.monadnock.org’ is known and matches the ECDSA host key.
debug1: Found key in /Users/me/.ssh/known_hosts:169
debug2: set_newkeys: mode 1
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS received
debug2: key: /Users/me/.ssh/gitlab_rsa (0x7fd901a00090), explicit
debug2: key: /Users/me/.ssh/gitlab_rsa (0x7fd901a000d0), explicit
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<rsa-sha2-256,rsa-sha2-512>
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /Users/me/.ssh/gitlab_rsa
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Offering RSA public key: /Users/me/.ssh/gitlab_rsa
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug2: we did not send a packet, disable method
debug1: Next authentication method: keyboard-interactive
debug2: userauth_kbdint
debug2: we sent a keyboard-interactive packet, wait for reply
debug2: input_userauth_info_req
debug2: input_userauth_info_req: num_prompts 1

~/.ssh/config

Host my.gitlab.server
HostName my.gitlab.server
User git
IdentityFile ~/.ssh/gitlab_rsa

gitlab info

Version: 9.1.4
Revision: fed799a
Directory: /opt/gitlab/embedded/service/gitlab-rails
DB Adapter: postgresql
URL: http://my.gitlab.server
HTTP Clone URL: http://my.gitlab.server/some-group/some-project.git
SSH Clone URL: git@my.gitlab.server:some-group/some-project.git
Using LDAP: no
Using Omniauth: no

GitLab Shell
Version: 5.0.2
Repository storage paths:

  • default: /remote_git/git2/repositories
    Hooks: /opt/gitlab/embedded/service/gitlab-shell/hooks
    Git: /opt/gitlab/embedded/bin/git

gitlab check

Checking GitLab Shell …

GitLab Shell version >= 5.0.2 ? … OK (5.0.2)
Repo base directory exists?
default… yes
Repo storage directories are symlinks?
default… no
Repo paths owned by git:git?
default… yes
Repo paths access is drwxrws—?
default… yes
hooks directories in repos are links: …
foo / bar_gitlab_test … ok
… ok
… ok
… ok
… ok
Running /opt/gitlab/embedded/service/gitlab-shell/bin/check
Check GitLab API access: OK
Access to /var/opt/gitlab/.ssh/authorized_keys: OK
Send ping to redis server: OK
gitlab-shell self-check successful

Checking GitLab Shell … Finished

Checking Sidekiq …

Running? … yes
Number of Sidekiq processes … 1

Checking Sidekiq … Finished

Checking Reply by email …

Reply by email is disabled in config/gitlab.yml

Checking Reply by email … Finished

Checking LDAP …

LDAP is disabled in config/gitlab.yml

Checking LDAP … Finished

Checking GitLab …

Git configured with autocrlf=input? … yes
Database config exists? … yes
All migrations up? … yes
Database contains orphaned GroupMembers? … no
GitLab config exists? … yes
GitLab config outdated? … no
Log directory writable? … yes
Tmp directory writable? … yes
Uploads directory setup correctly? … skipped (no tmp uploads folder yet)
Init script exists? … skipped (omnibus-gitlab has no init script)
Init script up-to-date? … skipped (omnibus-gitlab has no init script)
projects have namespace: …
foo / bar_gitlab_test … yes
… yes
… yes
… yes
… yes
Redis version >= 2.8.0? … yes
Ruby version >= 2.1.0 ? … yes (2.3.3)
Your git bin path is “/opt/gitlab/embedded/bin/git”
Git version >= 2.7.3 ? … yes (2.11.1)
Active users: 9

Checking GitLab … Finished