"Encrypt with the private key, so that it is decrypted with the public key": this is a flawed analogy, by which RSA signatures were first described, but even with RSA it does not work.
What you want is really a signature algorithm, however you want to call it. It is possible to define signature algorithms based on the RSA core operation, and it has been done, and it is called RSA. Anything which is RSA-based will involve some modular exponentiations working on, and yielding, big integers of the same size as the modulus. So a RSA-based signature with a RSA key worth that name (i.e. at least 1024 bits) will necessarily include a 1024-bit integer, so its size will not be lower than 128 bytes.
There is a possible twist in that RSA is a signature algorithm "with recovery": though the signature will have size at least 128 bytes, it is possible to embed in it some extra data (part of the message which is signed). There is a standard called ISO 9796-2 which does that; it has some shortcomings but it can be used. However, though this standard will make the total signature size overhead rather small, it won't please you, because you want to limit the size of that which is entered by a human user. The benefits of ISO 9796-2 are for long messages.
Algorithms producing short signatures are an active research area. Roughly speaking, if you target a security level of n bits (meaning: an attacker would have to invest in a computational effort of size 2n to be able to produce a fake signature -- but the effort may possibly enable him to produce millions of fake signatures for the same cost):
- With DSA and derivatives (e.g. ECDSA), the signature size is 4n bits.
- With BLS, the signature size is 2n bits (but the maths are hard to understand and there is no standard yet).
- There is an absolute theoretical minimum of n bits.
- We don't know good algorithms between n and 2n bits, although we know some of questionable security.
You might be able to fix that, though, by changing your models. Signature algorithms are meant for one thing: to allow someone to verify a signature without giving him the power to produce signatures. Depending on your exact context, it is possible that you do not really need this separation of roles. Maybe it is not a problem if whoever verifies a "signature" could potentially create signatures of his own. If that is the case, then you can use a MAC which can be considerably shorter (e.g. 32 bits might be sufficient in your case) and also much easier to implement (hint: use HMAC/SHA-256 and truncate to the desired size).