You could also deal with updating host keys by signing them and just having clients trust the signing authority.