Embodiments of a wireless device and methods for rekeying with reduced packet loss in a wireless network are generally described herein. In some embodiments, during rekeying operations a new key for reception may be installed early (i.e., prior to receipt of a rekeying confirmation message). The use of the new key for transmission may be delayed until after receipt of the rekeying confirmation message. The early installation of the new key for reception may allow both the new key and old key to be active at the same time for use decrypting received packets to reduce packet loss during rekeying operations. The rekeying confirmation message may be the fourth message of a four-way handshake for rekeying. In some embodiments, two key identifiers may be alternated between four-way handshakes to prevent deletion of the old key.