So by the picture you can see, Captain Johnson over by Fort Duvno gives me a quest to kill the commander of the Nephil Fort located to the north.

So I did, I killed Anastasia a "traitor to humandkind".

When I go back and talk to him he doesn't acknowledge the quest being done.

Did I get ahead of myself, is this normal, am I in the wrong place or is it a bug?

You went into entirely wrong fort. The Goblin Caves can be found by following the road north until you come to narrow passage then follow the wall left unit you come to a entrance on north wall (if you come to way north, you've come too far). The one you raided is for much later quest at Formello. The fort is piece of cake compared to one you already cleared being one of the first quest you're expected to complete.

[url=http://homepages.uni-regensburg.de/~mim09509/Avernum/Avernum1/Towns/EasternProvince.html]Here's map[/url]. It's marked with G on the map. WARNING: Contains spoilers