Enligt uppgift är det den före detta fängelsevakten Christo Brand, en av dem som jobbade på fängelset under Mandelas 18 år långa strafftid på ön, som lämnat in nyckeln.
Sydafrikas kulturminister Nathi Mthethwa säger i ett uttalande att det är "ofattbart" att den brittiska auktionsfirman Guernsey's tänker genomföra försäljningen.
"De är förstås medvetna om vårt lands smärtsamma historia och den starka symbol som nyckeln är. Den tillhör det sydafrikanska folket och borde finnas i Robben Island-museets ägo. Det är inte någons personliga ägodel", säger han.
Nelson Mandela fängslades i juni 1964, anklagad han för att ha planerat att störta den vita regimen i Sydafrika. 1982 förflyttades han från Robben Island till Pollsmoorefängelset och 1988 till Victor Verster-fängelset innan han frigavs 1990. Fyra år senare blev han landets president.