SIM card used as secure storage with AVR
literal answer

The "SIM Reader" and a few wires appears to be all the hardware needed to interface a SIM card to an Arduino.
There seem to be some Python scripts designed to talk to it over a serial port;
perhaps you wouldn't find it too difficult to translate to something (C++) that runs on an Arduino.


  Or should I just buy an ordinary smart card ...?


"A SIM card is a smart card." -- Thomas Pornin. "Is there cryptographic material in a phone's SIM card that can be used with RSA encryption?"

Most SIM cards today have "applications" that run on the little CPU in the SIM card stored in the flash of the SIM card.
-- "A brief introduction to the SIM-cards"

more general answer

No matter which chip the crypto software is running on, it seems better to generate and keep the key inside that same chip.

It seems to be easier to write software that implements public-key encryption to run on a AVR than to run on a smart card. If you run the crypto on the AVR chip, then it would be better to keep the secure key inside the AVR chip rather than try to store it externally.

Public-key encryption (combined with symmetric encryption like AES) seems to be more generally useful than any symmetric encryption system alone.
It sounds like you may be interested in the "Pico: No more passwords!" system; see also the early "Pico: No More Passwords!" video.