Как правильно авторизовываться по ssh?
Понимаете Вы все правилно.
Рутовый пароль вам будет нужен только для подключения локально ( не по SSH).
Для sudo вы используете не root password а пароль от своего пользователя (пароль рут нужен для  команды su)
Если вы потеряли ключ польззоателя - тогда авторизируетесь локально по паролю   и делаете новый ключь. 
 Если это VPS у них должна быть VNC сонсоль если дедик то IPMI
Использовать можете любого созданого вами  пользователя ( не забудте добавить его в sudousers) Линк 
Так же советую изменить ssh порт с 22 на какой-то другой 2022 к примеру. ( Боты восновном сканируют только стандартые порты)
Всё правильно понял. Единственное sudo, обычно, просит пароль пользователя, под которым ты запускаешь sudo, а не рута.Что в таком случае делать, если например, потерять приватный ключ пользователя?
Терять нельзя, это то же самое, что забыть пароль. Многие VPS-хостеры предоставляют доступ к терминалу через веб-интерфейс, в этом случае восстановить доступ через него. Если же такой возможности нет и нет физического доступа к серверу, то разве что горевать и писать в поддержку хостера.