The next few days using CM12 have been an awful experience, the OS was just slow, sluggish, unusable. I thought that it was all my own fault by installing a CM Nightly version instead of waiting for the first stable release.
I also installed the same CM12 Nightly on my Nexus 7 tablet at the very same time, but this device did not have these kind of issues. I dug a little bit into this, and as it turns out, the whole problem is the Cerberus App. Once uninstalled, the Nexus 5 was performing on the same satisfying level as the Nexus 7.
To uninstall the disguised version, I removed the apk in TWRP Recovery. First I mounted /system using the GUI, and removed the File via Terminal:
rm /system/priv-app/Cerberus.apk
Booting back into Android, I used the Android Terminal Emulator to uninstall the package. The Package Manager throwed some errors at me, nevertheless it looks like the uninstall has been completed.
su
pm uninstall com.lsdroid.cerberus