Provided are a computer program product, system, and method for generating public/private key pairs to deploy public keys at computing devices to verify digital signatures. A plurality of public-private key pairs are generated to store in a key store. A set of public keys of the public-private key pairs is distributed to the computing systems to use to verify purported digitally signed challenges. One of the public-private key pairs is selected to use a private key of the selected one of the public-private key pairs as a current private key to use to digitally sign challenges from the computing systems. A determination is made to retire the current private key. Another one of the public-private key pairs is selected and the current private key is set to a private key of the selected another one of the public-private key pairs to use to digitally sign challenges from the computing systems.