а нет ничего подозрительного в /var/lod/security на сервере?
не знаю что такое “шифровать домашний каталог”, но авторизация по ключам должна работать при первом логине

шифровать домашний каталог – это новая фича убунты, т.е. она хранит твой домашний каталог в зашифрованном файле/папке, а при логине монтирует его на место твоего домашнего каталога, для шифрования используется твой пароль, поэтому наверное когда в первый раз логинишься – оно не может вычитать authorized_keys (ибо твой хоум еще не подмонтирован) и поэтому оно запрашивает пароль.
В общем, имхо это фича нежели бага.

Там, вроде, при установке, когда выбираешь этот вариант, так и написано =)
Всмысле, что придется вводить пароль

ну я думал что не через ssh =) но видимо да, иначе он просто не может расшифровать домашний каталог :)