Když ztratíte klíč od domu, musíte vyměnit zámek u dveří. Když ztratíte privátní klíč, je to v principu stejné.
Musíte si vygenerovat novou kombinaci soukromého a veřejného klíče a na všechn službách, které tímto privátním klíčem odemykáte, musíte nastavit nový veřejný klíč. Soukromý klič si necháte jen u sebe a nikde jinde jej nenahráváte (ani na těch službách - tam jsou jen veřejné kliče).
Popsaná procedura odpovídá koupi nového zámku s klíčem a jeho instalace do dveří.
Pokud máte na soukromém klíči nastaveno dobré a dost dlouhé heslo (passphraze), není s výměnou takový spěch. Nicméně útočník může toto heslo časem prolomit (heslo je totiž mnohem kratší než samotný klíč), takže je výměna nutná. Pokud chcete bezpečnost, doporučuju používat delší passphraze, zakázat možnost zalogování na server heslem (nyní mluvím o ssh loginu) a ponechat jen login přes soukromý klíč.
Postup výměny klíčů je u každé služby jiný (u ssh typicky stačí vyměnit odpovídající řádek v ~/.ssh/authorized_keys + zkontrolovat, že se klíče neválejí někde jinde na serveru - jejich ponechání v ~/.ssh je typická chyba). Pro výměnu klíče není třeba resartovat sshd, při změně nastavení už pochopitelně ano. Pokud by byl kompromitován samotný server - útočník se nalogoval - je situace o několik řádů složitější, než při zprátě klíče bez nalogování útočníka.
Možná jsem na něco zapomněl - nechť mě někdo případně doplní.