The Efreeti are the Djinns I believe. You can find those easiest when you take the carpet in the camp at the entrance of the zone. (the mercenary camp, the carpet can be found near the mender there I believe)
Destination of the carpet is Giant's Fields. You'll find yourself right next to the sea and should be able to see a rock that is accessible by climbing down the cliffs. There are lots of solo djinns there (lvl 52, if memory serves me correctly), I've found all the parts needed there, and fairly swiftly too.
And for the Naga, well, in theory there should be solo Naga in PoF. I've never found those myself, so I just waited a bit and took out those heroic ones. Lowers faction though, but other mobs in that zone cancel that out.