少しはまったので、メモ。
Poderosa側は初期設定のまま。
まず、Niftyクラウドの管理画面で、サーバーを作成したときにダウンロードできる鍵ファイルを保存。
どっかからputtygen.exeを拾ってきて実行。
Conversionメニューから、Import Keyを選択。ダウンロードした鍵ファイルを指定する。
メインウィンドウのParametersのところで、Type of key to generateにSSH2-DSA、number of bits in generated keyのとこに4096を入力。
再びConversionメニューから、Export ssh.com keyを選択して、適当な名前で鍵ファイルを書き出す。
後は、Poderosaにこの鍵ファイルを与えれば無事接続。