Smart cities amalgamate technologies such as Internet of Things, big data analytics, and cloud computing to collect and analyze large volumes of data from varied sources which facilitate intelligent surveillance, enhanced energy management systems, and environmental monitoring. The ultimate goal of these smart cities is to offer city residents with better services, opportunities, and quality of life. However, the vulnerabilities in the underlying smart city technologies, interconnection of heterogeneous devices, and transfer of data over the open public channels expose these networks to a myriad of security and privacy threats. Therefore, many security solutions have been presented in the literature. However, the majority of these techniques still have numerous performance, privacy, and security challenges that need to be addressed. To this end, we present an anonymous authentication scheme for the smart cities based on physically unclonable function and user biometrics. Its formal security analysis using the Real-Or-Random (ROR) model demonstrates the robustness of the negotiated session key against active and passive attacks. In addition, the informal security analysis shows that it supports salient functional and security features such as mutual authentication, key agreement, perfect key secrecy, anonymity, and untraceability. It is also shown to withstand typical smart city threats such as side-channeling, offline guessing, session key disclosure, eavesdropping, session hijacking, privileged insider, and impersonation attacks. Moreover, comparative performance shows that it incurs the lowest energy and computation costs at relatively low communication overheads.