Methods are provided for decentralized key negotiation. One method includes initiating, by a first Internet Key Exchange (IKE) node from among a plurality of IKE nodes, a rekeying process for an Internet Protocol Security (IPSec) communication session established with a client device and serviced by a second IKE node from among the plurality of IKE nodes, and in which a first encryption key is used to encrypt traffic. The method further includes obtaining, by the first IKE node from a key value store, information about the IPSec communication session and performing, by the first IKE node, at least a part of the rekeying process in which the first encryption key is replaced with a second encryption key for the IPSec communication session.