A feature is provided that facilitates securely creating and/or replacing cryptographic keys. A first key pair is created comprising first private key and first public key. A second (spare) key pair is created comprising second private key and second public key. The second key pair is associated with the first private key. The second key pair is divided into shares and distributed to at least two shareholders. When the first key pair is to be replace, the second key pair is recreated and authenticated with at least a portion of the distributed shares. A trust level is associated with the second key pair corresponding to a trust level of the first key pair. The first key pair may be invalidated upon authentication of the second key pair. Further configurations provide for the creation of additional spare key pairs.