Вообщем проблему я решил. Внизу напишу как.
А пока прокомментирую и задам вопросы. Это для общего развития, т.к. сам нуб же.
По умолчанию она не под Linux ключ генерирует, я когда то на эти грабли наступил.
Надо было в linux генерировать.
Или заново генерируйте или через PUTTY gen конвертируйте под Linux.
Здесь не согласен. Что значит "ключ не под Linux"? RSA он и в африке RSA.
И ещё надо проброс ключа сделать, иначе не подключитесь.
Проброс можно с одного устройства сделать, потом только подтверждение будет выводиться на принятие ключа.(на других устройствах, которые проброс не умеют).
На каждом пробрасывать один и тот же ключ не надо.
Я на "андрюшке" не нашёл как пробросить, сделал с компа, дальше всё пошло хорошо.
Проброс - это доставка открытого ключа на сервер (в authorized_keys)?
Здесь тоже, мне кажется, неважно каким способом это сделать.
ssh-copy-id -i ~/.ssh/id_rsa.pub user@server
На андроиде я сделал также (под termux). В putty есть утилита psftp для этого. А можно же хоть ручками в authorized_keys забить, хоть на флешке скопировать?
snowin, jurganov,
от отключения авторизации по паролю ключ магическим образом не начнёт работать 
у меня на домашних машинах в локальной сети пароли разрешены, чтобы никто не мешал мне в случае нового юзера / новой машины подключаться по SSH
Согласен. Разрешенная авторизация по паролю не запрещает же авторизироваться по ключу. Просто приоритет по ключу выше. Пока у меня по ключу не работало, автоматом предлогало по паролю.
Мне помогло
sudo chmod 700 .ssh
sudo chmod 600 authorized_keys
Во тех мануалах, которых полно в интернете, ничего про это не говорится.
Заработало сразу и на винде и на андроиде. Всем спасибо!