I noticed the same thing. The game must use the fastest method of travel, which would be sea in your case.

I noticed whenever there wasnt a clear seazone link my loyalty would drop, as soon as their was a link, it would return to normal.