I don't think this problem is solvable as specified.
With a small message space, and deterministic hashing (or encryption), a generic attack involves exhaustively searching all likely messages to find one that corresponds to the known hash / ciphertext.
If all of the digits of the ID numbers were random, an exhaustive search would require about $10^{10} \approx 2^{33}$ iterations, and it might be feasible to use key stretching and/or rate-limited hardware to slow down the hashing enough to make such a search unfeasible.
Unfortunately, you say that some of the digits encode a date. If these ID numbers are anything like the local government IDs around here, I'm assuming something like 6 digits encoding a birthdate (in DDMMYY format, or similar) plus a four-digit sequence number. This reduces the necessary search space significantly:
Just the date format reduces the search space a lot: since there are only 356 valid dates in a year (or 366 for leap years), the actual number of valid IDs is only about $10^{8.4} \approx 2^{28}$.
If an attacker is targeting a specific person, they'll likely know the target's age to at least within a decade or so. This cuts the search space further down by a factor of (at least) 10.
In the worst case, the attacker already knows the target's age and birth date, and only needs to determine the last four digits of the ID. Thus, they only need to search $10^4 \approx 2^{13}$ ID numbers!
To make things even worse, the last four digits might not be random either. If they're instead assigned sequentially, lower numbers will be much more common, and so a sequential exhaustive search is likely to find the correct ID much sooner than one would expect if they were randomized.
Basically, in the worst-case scenario described above (which, really, isn't that far-fetched at all), no amount of key stretching will help: if your organization wants to be able to legitimately process more than one ID per minute, then a determined attacker with access to the same resources (which is a reasonable assumption, if internal attacks are a concern) and knowledge of the date part of the ID will be able to de-hash the ID in less than one week (= 10,080 minutes). If you need to be able to process one ID per second, the attacker only needs up to three hours. That holds regardless of the hashing or encryption method you're using, or the tools you use to implement it.
sha512sum
is not an algorithm, it's a GNU command line utility) and that with RSA you are referring to RSA / PKCS#1 v1.5 signature generation? Have you taken a look at PBKDFs? $\endgroup$ – Maarten Bodewes♦ May 21 '15 at 11:49