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 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 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. We also consolidate the performance information of those protocols to show the runtime and storage cost when employing varying number of authentication factors.