I finally found it!

I set up an self-hosted gitlab at our company and for some reason everything worked except for one thing: using git (clone, push, etc) via SSH.
The solution was on the 'common installation problems' page at gitlab, but it took me a long time finding it through Google.
I read through the auth.log and realized the 'git' user was locked. Swapped the '!' for a '*' in the /etc/shadow and now it works.