Как с помощью ssh ключей с машины, на которой я пользователь, подключиться к машине, на которой нужно работать под root?
Проверьте файл /root/.ssh/authorized_keys на содержание необходимого публичного ключа.
Всё, разобрался. Нужно было в /etc/ssh/sshd_config добавить следующую строку:StrictModes no
никакие остальные параметры в конфиге можно вообще не менять. 
Еще важно выполнить на том хосте, с которого подключаетесь команду:$ ssh-add