Das eigentliche Problem war, dass mein Benutzer irgendwie in `/etc/shadow fehlte.
Ich werde diese Frage für einige Zeit offen lassen, damit die Leute hier weitere Ratschläge zur Fehlerbehebung geben können.
Stellen Sie außerdem sicher, dass die Berechtigungen für ~/.ssh 700 und ~/.ssh/authorized_keys 600 sind. Der Server lässt Sie den Schlüssel nicht verwenden, wenn die Berechtigungen falsch sind.