As promising altatives in building future main memory systems, emerging non-volatile memory (NVM) technologies can increase memory capacity in a cost-effective and power-efficient way. However, NVM is facing security threats due to its limited write endurance: a malicious adversary can wear out the cells and cause the NVM system to fail quickly. To address this issue, several wear-leveling schemes have been proposed to evenly distribute write traffic in a security-aware manner. In this study, we present a new type of timing attack, remapping timing attack (RTA), based on information leakage from the remapping latency difference in NVM. Our analysis and experimental results show that RTA can cause three of the latest wear-leveling schemes (i.e., region-based start-gap, security refresh, and multi-way wear leveling) to lose their effectiveness in several days (even minutes), causing failure of NVM. To defend against such an attack, we further propose a novel wear-leveling scheme called the ’security region-based start-gap (security RBSG)’, which is a two-stage strategy using a dynamic Feistel network to enhance the simple start-gap wear leveling with level-adjustable security assurance. The theoretical analysis and evaluation results show that the proposed security RBSG not only performs well when facing traditional malicious attacks, but also better defends against RTA.