The globalization of the semiconductor industry has caused many challenges to prevent intellectual property (IP) piracy. Logic encryption is an effective technique for hardware IP protection. Researchers have proposed various logic encryption techniques, which introduce large overheads in delay, power and area. This paper aims to significantly reduce these overheads by proposing a novel gate replacement-based implementation. A simulated annealing algorithm is adopted to find the optimal replacement positions. Experimental results show that our implementation reduces 15% to 30% of the area overhead, and 60% to 80% of the delay and power overheads, while the encryption quality is almost not degraded. The idea of gate replacement can be applied to various XOR/XNOR-based logic encryption approaches.