You don't have to find Caracalla my friend, just his corpse to get the key.

Just look for his corpse at the Great Market Square. It's the only burning corpse which has two champions standing guard over it, and a lady mourning near it.