Algorithm agility is bad. You see it happening at the beginning of every TLS session; what you don't see are the long trail of vulnerabilities that have resulted from TLS's overly complicated handshake, and, worse, the essentially nonexistent vulnerabilities algorithm agility has mitigated over TLS's lifetime; in general, when TLS constructions have failed, they've failed in the joinery (block cipher modes, MAC arrangements, etc), and, most importantly, have required updates to the entire protocol anyways.

It's a bad idea and people shouldn't build it into new systems. Version the protocol instead, and plan on making it straightforward to upgrade the protocol and lock out old versions.