A sanitizable signature scheme is a malleable signature scheme where a designated third party has the permission to modify certain parts of the message and adapt the signature accordingly. This primitive was introduced by Ateniese et al. (ESORICS 2005) and Brzuska et al. (PKC 2009) formalized the initially suggested five security properties. In the subsequent year, Brzuska et al. (PKC 2010) introduced a notion called unlinkability where the basic idea is that linking message-signature pairs of the same document should be infeasible. Brzuska et al. formalized this notion and suggested a generic instantiation based on group signatures with a special structure. Unfortunately, the most efficient instantiations of group signatures do not have this property. In this work, we present the first efficient construction of unlinkable sanitizable signatures based on a novel type of signature schemes with re-randomizable keys. This property allows one to re-randomize both the signing and the verification key separately but consistently. Given a signature scheme with re-randomizable keys, we obtain a sanitizable signature scheme by signing the message with a re-randomized key and proving in zero-knowledge that the derived key originates from either the signer or the sanitizer. To obtain an efficient instantiation, we instantiate this generic idea with Schnorr signatures and efficient -protocols that we turn into a non-interactive zero-knowledge proof via the Fiat-Shamir transformation. In this work, we present an optimized version that is more efficient than the construction we suggested in the extended abstract of this work at PKC 2016.