With the rapid growth of Internet of Things (IoT) applications, Fog computing gained a great attention providing IoT data processing locally at fog nodes instead of sending them to the Cloud to provide faster responses to IoT applications compared to using Cloud servers (CS). In order to enhance performance, and reduce bandwidth consumption, Software Defined Network (SDN) is integrated with Fog computing to provide SDN-based Fog-IoT network. This SDN-based Fog-IoT network is subject to many attacks. This paper addresses the authentication and privacy between the nodes using lightweight algorithms to cope with the constrained nature of IoT devices through the use of Elliptic Curve Diffie–Hellman Ephemeral (ECDHE) key exchange algorithm along with the Pre-Shared Key (PSK) as a lightweight and secure authentication scheme between the Cloud servers and IoT devices. The SDN controller is used to probably allocate the appropriate Fog node to serve the IoT device. The Key Distribution Server (KDS) integrated in the CS is responsible for generating the keys used to secure the channel between Fog nodes and IoT devices. The proposed scheme is mathematically evaluated relative to state-of-the-art protocols and certificate-based authentication schemes. The analysis showed that the proposed scheme is light and scalable compared to other schemes.