One of the challenges to secure Wireless Sensor Networks (WSNs) is to design secure pair-wise key agreement between any pair of resources-limited sensors while keeping strong connectivity. In this paper, we point out the fatal security weaknesses of Cheng-Agrawal’s pair-wise key agreement scheme for WSNs, and then propose a new scheme. Compared to the existing schemes, the proposed scheme owns two outstanding merits- assurance of connectivity between any pair of nodes and security robustness against node capture attack.