To enable enhanced accountability of Unmanned Aerial Vehicles (UAVs) operations, the US-based Federal Avionics Administration (FAA) recently published a new dedicated regulation, namely RemoteID, requiring UAV operators to broadcast messages reporting their identity and location. The enforcement of such a rule, mandatory by 2022, generated significant concerns on UAV operators, primarily because of privacy issues derived by the indiscriminate broadcast of the plain-text identity of the UAV on the wireless channel. In this paper, we propose ARID, a solution enabling RemoteIDcompliant Anonymous Remote Identification of UAVs. The adoption of ARID allows UAVs to broadcast RemoteID-compliant messages using ephemeral pseudonyms that only a Trusted Authority, such as the FAA, can link to the long-term identifier of the UAV and its operator. Moreover, ARID also enforces UAV message authenticity, to protect UAVs against impersonation and spoofed reporting, while requiring an overall minimal toll on the battery budget. Furthermore, ARID generates negligible overhead on the Trusted Authority, not requiring the secure maintenance of any private database. While the security properties of ARID are thoroughly discussed and formally verified with ProVerif, we also implemented a prototype of ARID on a real UAV, i.e., the 3DR-Solo drone, integrating our solution within the popular Poky Operating System, on top of the widespread MAVLink protocol. Our experimental performance evaluation shows that the most demanding configuration of ARID takes only ≈ 11.23 ms to generate a message and requires a mere 4.72 mJ of energy. Finally, we also released the source code of ARID to foster further investigations and development by Academia, Industry, and practitioners.