One of the concerns that comes with the use of RFID tags is that these respond to any query. This can be overcome by having mutual authentication between reader and tag. However, the ordering between the two authentication steps is crucial. In this paper, we formalise mutual RFID authentication: capturing the necessary coupling between tag authentication and reader authentication as well as the ordering between these authentication steps. We show that the reader needs to authenticate first to the yet unknown tag to 1) preserve the tag's privacy, 2) make it more resistant to side-channel analysis and 3) ensure that the end-user can observe the protocol's output. We propose a generic construction to transform existing private RFID authentication protocols into proper private RFID mutual authentication protocols. Finally, we design a very efficient wide-strong private RFID mutual authentication protocol that requires the tag to compute only three scalar-elliptic curve point multiplications. We also show how this new protocol can be implemented efficiently in hardware.