Где лежит публичный ключ сервера?

ты пиши чтоль заранее какое подключение подразмеваешь под " захожу на сервер".

/etc/ssh/sshd_config параметр HostKey указывает на файлы, с закрытой частью ключа.
рядом лежит .pub с открытой частью. один из них, в зависимости от того, до какого протокола договорятся клиент с хостом.

Извините :) Спасибо, действительно ключ лежит в ssh_host_rsa_key

Что бы можно было его перед первым подключением его добавить на клиенте?

Думаю тебе нужен ssh-keyscan, ну или StrictHostKeyChecking no если с безопасностью не заморачиваешься