...I found it exploring the beginning of the fjords before heading to Sentinel Island.
Since I know that there's a key down there from my first playthrough, I first go pick it up with my following characters, before I head upstairs. Saves me a trip.
p.s. In DKS