鍵+パスフレーズを利用してsshを利用しているのですが、
ログインに時間がかかります。
12、13秒ほどかかります。

これって、こういうものですか？

鍵は、DSA 768bitです。
パスフレーズは、8文字程度です。