今に始まった話じゃないんです。
sshのクライアントを変えたりServerになる側を変えたりするたびに、毎回詰まっている気がするので、今後の備忘録として書いておきます。

最初に要約すると、Androidで利用できるsshクライアントのJuiceSSHは最近のOpenSSHの秘密鍵には対応してませんよ～ってこと。
じゃどうするの？って言うのは、古い形式の秘密鍵を使うしかなさそうね。ってこと。

ServerのOSも新しくして、sshも入れて公開鍵認証で設定してWindows側で使用しているrLoginで問題なくログイン出来る様にはなるんですよね。
で、同じ秘密鍵をAndroid端末にコピーしてJuiceSSHでログインしようとすると、「無効なプライベートキー」とか言われて認識してくれない。

と、いうここまで定型で、たぶん４・５回遭遇してます。。。そして、なんやかんやでうまく行ってうまく行った理由を覚えてない。。。
なので、なんでうまく行ってないのかとかちゃんと調べてみた。

JuiceSSH Supported Private Key Formats (OpenSSH PEM)

It reveals that the criteria for being recognised as a valid key file are:

File size < 8kb
First 37 chars contain one of:
　　"-----BEGIN RSA PRIVATE KEY-----"
　　"-----BEGIN DSA PRIVATE KEY-----"
　　"-----BEGIN PRIVATE KEY-----"
　　"-----BEGIN ENCRYPTED PRIVATE KEY-----"

まぁ、答えはこれですね。JuiceSSHでは秘密鍵のヘッダが上の4種類でしか認識しない様です。で、最近のOpenSSHはと言うと秘密鍵を開いてみるとわかりますが、

-----BEGIN OPENSSH PRIVATE KEY-----

じゃぁ、どうするのかというとssh-keygenで鍵を作成する際に、「-m PEM」をオプションで追加する事で、古い形式にて出力してくれるようです。