Clone Node Attack is the most perilous threat to the security of wireless sensor networks. In this attack, an adversary compromises the captured node and replicates it, creating many replicas with the same node identity by obtaining all the secrets of the nodes. After this an adversary may launch many insidious attacks within the sensor network. Recent studies have shown that Randomized, Efficient and Distributed (RED) is considered to be the most promising distributed solution for detecting clone nodes but it also has some uncompromising shortcomings. In this paper we have presented a distributed, non-deterministic solution called Temporal Key Based RED (TKRED) which removes the drawbacks of RED by making enhancements in order to identify and revoke clones. Our simulation results have shown that proposed modification makes the protocol TKRED fully distributed and the witness node selection is non-deterministic.