A user in Beyond 3rd Generation (B3G) networks in order to get access to the network services must perform a multi-pass authentication procedure, which includes two or three sequential authentications steps. These multiple authentication steps include a redundant repetition of the same or similar authentication functions, which impose an unnecessary authentication overhead. This paper proposes a security binding mechanism, which reduces the execution of the redundant authentication functions of multi-pass authentications in a simple yet effective and secure manner. To achieve this, the proposed mechanism authenticates a user in the second and third step of a multi-pass authentication, by using the user's authentication credentials of the initial step. The focal point of the security binding mechanism is its generic application in multi-pass authentications, regardless of the underlying network architecture or protocols. To prove this, we have selected to present and analyze the application of the proposed mechanism in two different B3G scenarios (i.e., 3G-WLAN and WiMAX), resulting in the improved authentication procedures. A security analysis of the improved procedures has been carried out to identify possible attacks and propose security measures to eliminate them. Moreover, a simulation model has been developed to estimate and compare the performance of the improved 3G-WLAN authentication procedure to that of the legacy 3G-WLAN authentication. Simulation results show that the improved procedure presents better performance than its legacy counterpart.