In one embodiment, apparatus and methods for a rekey process are disclosed. In certain rekey embodiments, when a key-generation protocol exchange is executed, instead of generating a single new security relationship, such as a Security Association or SA, a multiple set (e.g., 10) of new security relationships (e.g., SAs) are generated. An authorized device can then individually use these security relationships (e.g., SAs) as needed to securely communicate with each other. For example, a set of SAs can be efficiently programmed into an 802.1ae protocol ASIC for handling transmitted and received data packets. In the description herein, embodiments of the invention are described with respect to SA's, and this “SA” term is generally defined as any type of security relation that can be formed to allow a particular node to securely transmit packets or frames to another receiving node.