Unmanned Aerial Vehicle (UAV) plays a paramount role in various fields, such as military, aerospace, reconnaissance, agriculture, and many more. The development and implementation of these devices have become vital in terms of usability and reachability. Unfortunately, as they become widespread and their demand grows, they are becoming more and more vulnerable to several security attacks, including, but not limited to, jamming, information leakage, and spoofing. In order to cope with such attacks and security threats, a proper design of robust security protocols is indispensable. Although several pieces of research have been carried out with this regard, there are still research gaps, particularly concerning UAV-to-UAV secure communication, support for perfect forward secrecy, and provision of non-repudiation. Especially in a military scenario, it is essential to solve these gaps. In this paper, we studied the security prerequisites of the UAV communication protocol, specifically in the military setting. More importantly, a security protocol (with two sub-protocols), that serves in securing the communication between UAVs, and between a UAV and a Ground Control Station, is proposed. This protocol, apart from the common security requirements, achieves perfect forward secrecy and non-repudiation, which are essential to a secure military communication. The proposed protocol is formally and thoroughly verified by using the BAN-logic (Burrow-Abadi-Needham logic) and Scyther tool, followed by performance evaluation and implementation of the protocol on a real UAV. From the security and performance evaluation, it is indicated that the proposed protocol is superior compared to other related protocols while meeting confidentiality, integrity, mutual authentication, non-repudiation, perfect forward secrecy, perfect backward secrecy, response to DoS (Denial of Service) attacks, man-in-the-middle protection, and D2D (Drone-to-Drone) security.