The way to accommodate a new key size or algorithm is to say “v2 of the protocol will use $key_size and $cipher, and will not use $old_key_size or $old_cipher. Upgrade to this version due to $reason_old_setup_is_obsolete”. A casual observation of history will find that attempting to build negotiation of security features into a protocol is akin to opting in to a fun, optional class of major security vulnerability. For reference: SSL/TLS, GPG.
Not necessarily. You can also tie algorithms to keys. For example, if you want to verify a signature, it’s perfectly reasonable for the public key to actually be (algorithm, private key as defined by that algorithm). What you don’t want to do is put the algorithm in a message that is potentially controlled by an attacker.
