Nowadays, cyberattacks are growing exponentially, causing havoc to Internet users. In particular, authentication attacks constitute the major attack vector where intruders impersonate legitimate users to maliciously access systems or resources. Traditional single-factor authentication (SFA) protocols are often bypassed by side-channel and other attack techniques, hence they are no longer sufficient to effectively address the current authentication requirements. To alleviate this problem, multi-factor authentication (MFA) protocols have been widely adopted recently, which helps to raise the security bar against imposters. Although MFA is generally considered more robust and secure than SFA, it may not always guarantee enhanced security and efficiency. This is because, critical security vulnerabilities and performance problems may still arise due to design or implementation flaws of the protocols. Such vulnerabilities are often left unnoticed by the designers or users until they are exploited by attackers. Therefore, the main objective of this work is identifying such vulnerabilities in existing MFA protocols by systematically analysing their designs and constructions. To this end, we first form a set of security evaluation criteria, encompassing both existing and newly introduced ones, which we believe are very critical for the security of MFA protocols. Then, we thoroughly review several MFA protocols across different domains. Subsequently, we revisit and thoroughly analyze the design and construction of the protocols to identify potential vulnerabilities. Consequently, we manage to identify critical vulnerabilities in ten of the MFA protocols investigated. We thoroughly discuss the identified vulnerabilities in each protocol and devise relevant mitigation strategies for each of the vulnerabilities identified. We also consolidate the performance information of the protocols. We believe that the consolidated security analysis and performance information would serve as a single reference point for researchers and practitioners to be aware of the potential security and performance issues when designing MFA protocols. This investigation also reinforces the fundamental need for an enhanced and secure design and implementation of MFA protocols.