The hostkey algorithm should be decided based on security policy. The new host key with different algorithm could be taken into active use faster in the environment than using the same algorithm as the current host key but it may cause unexpected key exchange failures if the different algorithms are not allowed in configuration.
While Tectia Server can have multiple identities, the client and server can only agree on one hostkey algorithm during key exchange in secure shell protocol. The negotiated algorithm depends on what the server offers and what the client supports and prefers in its configuration and what type host key(s), if any, it has saved to known hosts for the server.
For example if Tectia Server has currently RSA hostkey and new host key is generated with different algorithm for example ECDSA or ED25519 both can be enabled simultaneously as current hostkey identities. Clients that connect the first time may already use the new hostkey but clients that prefer or only support RSA or clients that have connected before continue to use the RSA hostkey as long as the server has it enabled and offers it in key exchange.
Tectia Server can be configured so that current RSA hostkey is enabled but not advertised and the new hostkey of different algorithm is both enabled and advertised. This allows secure shell clients that have connected before and support and enable Host Key Rotation / UpdateHostKeys to connect once and authenticate the server with RSA hostkey and after successful user authentication to add the advertised hostkey and remove the old RSA hostkey from known hosts within the same connection. For subsequent connections by this client the new hostkey is used provided that the client allows it in configuration.
If the same algorithm is used for the new host key, for example current hostkey is RSA and new RSA hostkey is generated, then only the first one is enabled as hostkey identity. In this case Tectia Server must be configured so that current RSA hostkey is enabled and advertised and the new RSA hostkey is advertised. This ensures secure shell clients that support and enable Host Key Rotation / UpdateHostKeys can connect and authenticate the server with current RSA hostkey and after successful user authentication add the advertised hostkey for future use when the old RSA hostkey is removed from Tectia Server.