The introduction of smart grids as the next generation of the traditional power grids, presents new features and solutions for an intelligent and efficient power generation and distribution. The Advanced Metering Infrastructure (AMI) is an important component of the smart grid where user and administrative data will be constantly exchanged between the different parts of the smart grid to assure its work continuity, and efficiency. This constant flow of information will regulate, and adjust the power generation and distribution process to the most efficient way. Even though smart grids offers huge economic and environmental benefits, critical security and privacy concerns exists. Securing the system against these issues will be crucial. The smart grid security and in particular the AMI security require the implementation of security schemes and protocols that rely on cryptographic mechanisms that use encryption and decryption keys. This makes the presence of a key management scheme a critical requirement for AMI and thus for smart grid security. The key management scheme should meet generic requirements (applied for all key management schemes) as well as additional requirements specific to smart grid systems, in a way that it secures the system without affecting its performance. This research work analyzes the different key exchange mechanisms proposed in the literature to secure the AMI of the smart grid, showing their advantages and disadvantages and their extent of suitability to the specific requirements of the smart grid. Based on the analysis, a complete key exchange scheme is designed for the AMI using efficient and secure key generation and refreshing techniques that maintains a high level of security and efficiency with less computational and communicational overheads preserving its scalability.