Algorithms for Authenticated Encryption with Associated Data (AEAD) extend the normal functionality of authenticated encryption schemes by the ability to process data that is only authenticated but not encrypted. Such algorithms have attracted much interest in the past few years, especially the question of how they can be designed and implemented efficiently to perform well in resource-constrained devices like miniature sensor nodes or RFID tags. In this paper, we analyze the performance of the lightweight AEAD schemes Elephant v2, Grain-128AEADv2, ISAP v2.0, PHOTON-Beetle, and Romulus v1.3 on the MSP430 family of 16-bit ultra-low-power microcontrollers. All five have in common that they offer large security margins and made it into the last round of the Lightweight Cryptography (LWC) standardization project of the U.S. National Institute of Standards and Technology. We describe how these AEAD algorithms can be implemented efficiently in software and introduce Assembly-level optimization techniques for the underlying primitives, which include three permutations, one tweakable block cipher, and one stream cipher. Furthermore, we present numerous detailed benchmarking results (i.e., execution time and code size) for the primitives as well as for the full AEAD algorithms for different lengths of plaintext and associated data. Our benchmarks clearly show that all five AEAD algorithms are much more efficient (up to almost two orders of magnitude) on MSP430 than indicated by results in the literature.