El problema real era que mi usuario de alguna manera no estaba en `/etc/shadow.
Dejaré que esta pregunta permanezca abierta durante algún tiempo para que las personas puedan agregar más consejos para la solución de problemas aquí.
Además, asegúrese de que los permisos en ~/.ssh sean 700 y ~/.ssh/authorized_keys sea 600. El servidor no le permitirá usar la clave si los permisos son incorrectos.