The Key is located not far from the DarkIce Mines' landing site. Fox has to make use of Prince Tricky's Find Command to reveal a tunnel into the very first building. Two SharpClaw guard the contraption, unlockable with the Krystal's Staff, holding the key. It is used to free one of the SnowHorns from leg shackles right outside one of the buildings. The SnowHorn begs Fox to rescue Belina Te and rewards him with first of the four Bridge Cogs.
"This is a Shackle Key. Use it to unlock SnowHorn Leg Shackles."