A SIM card is a smart card. It follows all the relevant standards for smart cards, it is produced by smart card vendors.
A smart card is "just" a tamper-resistant computer. It has its own CPU, RAM, ROM, storage area (often EEPROM). Power and clock are provided from the outside. The device is supposed to be resistant to physical extraction of the internally stored data: it is equipped with a lot of sensors which detect a breach of the outer cover, operations in out-of-range conditions (temperature too low or too high, clock rate departing from the expected frequency...), and, ultimately, should self-destruct if advanced reverse engineering is attempted on it.
Of course, this is all a question of money. Direct inspection with an electron microscope and lasers is said to cost a few thousands of dollars; in past years, it was quite an industry among satellite pay-TV hackers (especially in countries which received the signal from the satellite but could not legally subscribe for lack of a commercial infrastructure -- I saw it happen a lot in North Africa, with European TV). Also, investigation methods for the extraction of secret key from a smart card have been seriously studied by both academics and the industry. Finally, a smart card being a small computer in its own right, it uses software and thus has bugs, some of which being exploitable.
I have recently worked with that kind of product. This is a smart card which can fit in the "SIM format" and yet can store and use dozens of RSA keys. The keys are generated on board, and performance is quite acceptable for many usages (less than 1 second for a 2048-bit RSA signature). The card has been certified to conform to FIPS 140-2 Level 3 and EAL 5+, which are both rather impressive (they don't guarantee that the card is unbreakable, but they demonstrate that the vendor had least invested substantial efforts and money towards that goal).
What I explain above is that it is technologically possible to have a SIM-like card which stores and use asymmetric keys for cryptography, with a resistance to private key extraction which is not negligible.
Now, of course, the problem is that existing, deployed SIM cards are not necessarily able to do that. The core functionality of a SIM card is to store a symmetric key and use it for an authentication protocol with the phone provider network. This is called A3/A8 in the GSM world. This is symmetric cryptography only, which is computationally much easier and can be done with a basic 8-bit CPU, not requiring any accelerator circuitry. Such cards are quite cheaper than RSA-able smart cards, and phone companies are known to always try to lower their costs as much as possible (order of magnitude for the production cost of an individual card is around 5$ for a RSA-able card, less than 1$ for a card which does only symmetric crypto).
Some companies have deployed SIM cards which can compute signatures, but I don't think you can expect it from most existing SIM cards (yet). The technology is there, now a commercial incentive is needed.
A further complication is whether access from an Android app would be allowed. Within a phone, the SIM card is quite isolated, because it is used as the legal basis for communication billing: if the card can be hijacked from a malware app, then it becomes too easy for customers to claim that their phone was hacked and then refuse to pay their bills.
You don't "encrypt with the private key". With a private key, you decrypt or you sign. I suppose your use case is that of authentication: you want to make sure, from the server, that a specific user is on the other end of the line.
