A visszafejtési idő nagyon függ a kulcs hosszától. De a kódolt jelszó az su-s (sudo-s) megoldás esetén is átmegy, amikor a su-hoz írod be a jelszót, csak kódolt adatforgalomként.
Ha (nagyjából) biztosra akarsz menni, akkor a usernek hosszú kulcsot generálsz, a szerver nyilvános kulcsát és a saját titkos kulcsodat pedig pendrive-on magaddal viszed. Ha be akarsz jelentkezni, akkor először ellenőrzöd, hogy a szerver az-e, akinek mondja magát (man in the middle attack kizárása, a szerver kulcsa ahhoz kell, hogy ellenőrizd, hogy nincs-e félúton valaki, aki elkapja, amikor bejelentkezel, és aztán bent van a nevedben; erre szolgál a .ssh/known_hosts file), majd a saját kulcsoddal authentikálsz (ez már megy úgy, hogy a kulcsod nem megy át a hálón, még kódoltan sem, hiszen elég azt ellenőrizni, hogy a szerver elkódol valamit a nyilvános kulcsoddal, és te vissza tudod-e küldeni a szerver nyilvános kulcsával kódoltan, azaz, ha meg tudod mondani, mi volt egy kódolt üzenetben, akkor már biztos, hogy rendelkezel a titkos kulcsoddal).
Természetesen, ha valaki talál egy gyors (polinomiális idejű) prímfaktorizációs eljárást, akkor ennek lőttek, de ezen én egyelőre nem nagyon aggódnék.