Проблема был такая: Открывая консоль putty, я начинал вводить логин root, но язык стоял русский и я вводил кщще, после этого стирал и вводил заново. Оказывается так делать нельзя.
У вас там при авторизации в имя пользователя пробел лишний попал, скорее всего.
Рутовый пабключ (и проверьте, что это именно пабключ, а не его закрытая часть) нужно класть в файл /root/.ssh/authorized_keys.