Начинаем работу со стороны сервера. Пробовал генерацию со стороны клиента — тупик.
Для начала генерируем ключи от пользователя для которого все это делается
ssh-keygen -b 2048 -C "some comment"
В первый раз создаем файл с ключами
cd .ssh/
touch authorized_keys
Добавляем сгенерированный ключ
cat id_rsa.pub >> authorized_keys
Сервер готов.

Клиент. Я сижу с винды из Putty. Она использует свой формат, потом надо ключики конвертить.
Качаем id_rsa на комп (файлик, что без расширения). Открываем в puttygen. В меню выберите пункт Conversion, а в нём — Import key. Найдите ваш закрытый ключ и откройте его. Если ранее вы указали парольную фразу, сейчас её нужно будет ввести для открытия ключа. Нажмите кнопку Save private key
Дайте подходящее имя закрытому ключу и сохраните его куда-нибудь. Как видите, формат файла изменился — теперь он ppk.
Создайте в Putty новое подключение. В настройках найдите пункт Auth. На этой странице в поле Private key file for authentication выберите сохранённый ключ.

Если появляется проблема — первое, что делаем — проверяем права на файлы (а точнее сразу выставляем нужные)
chmod go-w ~/
chmod 700 ~/.ssh
chmod 600 ~/.ssh/authorized_keys

В случае с линуксом можно скопировать публичный ключ на удаленную машину
ssh-copy-id -i ~/.ssh/id_rsa.pub root@server2