Você não precisa alterar as chaves se não tiver motivos para acreditar que elas foram comprometidas.
Se você sempre se conectar ao host por meio de seu nome de host DNS, seus clientes SSH provavelmente não perceberão nenhuma diferença. Se você se conectar por meio do endereço IP e agora o servidor estiver em um endereço IP diferente, seus clientes perguntarão se você deseja confiar nesse host, como se estivessem se conectando a um novo host.