Current collision avoidance techniques deployed on Unmanned Aerial Vehicles (UAVs) rely on short-range sensors, such as proximity sensors, cameras, and microphones. Unfortunately, their efficiency is significantly limited in several situations; for instance, when a remote UAV approaches at high velocity, or when the surrounding environment is impaired (e.g., fog, noise). In the cited cases, to avoid collisions and maintain self-separation, UAVs often rely on the indiscriminate broadcast of their location. Therefore, an adversary could easily identify the location of the UAV and attack it, e.g., by physically shutting it down, launching wireless jamming attacks, or continuing tracking its movements. To address the above-introduced threats, in this article we present PPCA, a lightweight, distributed, and privacy-preserving scheme to avoid collisions among UAVs. Our solution, based on an ingenious tessellation of the space, is accompanied by a thorough analytical model and is supported by an extensive experimental campaign performed on a real 3DR-Solo drone. The achieved results are striking: PPCA can efficiently and effectively avoid collisions among UAVs, by requiring a limited bandwidth and computational overhead (84.85% less than traditional privacy-preserving proximity testing approaches), while providing unique benefits in terms of privacy of the participating UAVs.