> 1. То есть кроме как своя машина и интернет-кафе других вариантов у
> вас нет? Мои соболезнования.

Можно иметь приватный ключ и не на основной машине.
При желании, можно наделать несколько приватных ключей, свой на каждом компьютере.
Если какой-то компьютер скомпрометрируют, достаточно будет отозвать его ключ.

> 2. Сгенерить и отправить приватный ключ, а клиент его себе установит как
> дефолтный?

А вот тут мы подходим к ощущению, что вы с ключами не особо игрались.
Можно иметь кучу ключей, особенно удобно при этом использовать ssh-agent, который держит эти ключи в памяти и пробует их при подключении.
По умолчанию пробуются все ключи, можно настроить, чтобы для конкретного сервера использовать конкретный ключ.

> А вообще речь шла о хостерах. Все кто мне до сих пор
> встречался, передавали сервер именно через логин/пароль на ssh и никто не
> предлагал вариант заслать им публичный ключ.

В хостинге своя тема - там публике лишь бы что попроще и постарше. Спокойно держатся php 5.2, 5.3. Доступ к файлам по ftp. Даже ssh не все просят, потому что не все про него знают. Хостинго-держатели по своей инициативе стараются не пугать людей незнакомыми словами, поэтому и дают по умолчанию самый простой доступ - ftp и ssh (и то не всегда говорят про ssh). Но на некоторых хостингах я встречал возможность самому положить публичный ключ и ходить по ключу.