send_pubkey_test: отсутствует общий алгоритм подписи

Просто хотел сказать спасибо!! Это здорово сэкономило мне время.

В моём случае новый сервер на Ubuntu 22.04, на который я мигрировал, отказывался использовать файл с ключом, хотя я и использовал правильный синтаксис. Флаг -vv в команде SSH показал, что алгоритм подписи не принимается. Создайте новый файл в /etc/ssh/ssh_config.d, назовите его как угодно с расширением .conf, и, как уже советовали, добавьте одну строчку: PubkeyAcceptedAlgorithms +ssh-rsa. Также можно сразу проверить это прямо в команде SSH, добавив опцию -o PubkeyAcceptedKeyTypes=+ssh-rsa перед созданием файла. У меня сработало.

Как упомянул @eworm в другой ветке, начиная с Router OS 7.7 поддерживаются ключи ed25519, из списка изменений:  
*) ssh — добавлена поддержка обмена ключами Ed25519;  
*) ssh — запрет использования SHA1 при включённой сильной криптографии;  
*) ssh — исправлена обработка RSA-ключей нестандартного размера;  

Так что можно создать новый ключ вот так: ssh-keygen -t ed25519 -b 4096

Это неправда. Я этого не писал. На данный момент поддерживается только обмен ключами ed25519. Будем надеяться, что вскоре появится поддержка хост-ключей и аутентификации по открытым ключам.

Обновление по теме. Сегодня я обновил свой SSH-клиент, и теперь эти настройки больше не работают: HostKeyAlgorithms +ssh-dss PubkeyAcceptedAlgorithms +ssh-rsa Результат такой: /home/user/.ssh/config строка 6: Неверный тип ключа '+ssh-dss'. /home/user/.ssh/config: завершение работы, 1 неверная опция конфигурации. Похоже, что с KexAlgorithms +diffie-hellman-group1-sha1 на RouterOS 7.15 всё работает, но про более старые версии я не уверен.