Iterative insertion gives a time complexity of $O(n \log n)$ for $n$ keys, but it's possible to do it in linear time.
The input tree gives you the in-order traversal, so you can begin by traversing the input tree and storing the keys in an array. Now, notice that if $n = 2^m - 1$ for some $m$, it's actually trivial to create a new binary tree which is perfectly balanced: split the array in half, choose the middle element as the root, and recursively build the left and right children from the two halves of the array. To make it a red-black tree, you have to assign colors. For a perfectly balanced tree, this is simple: you can actually make every node black.
But how do you handle the general case, when $n$ is not one less than a power of 2? You won't be able to make a perfectly balanced tree, but you can get pretty darn close!
This smells like a homework assignment, so I'll leave the specifics of assigning colors to you, but here's something to get started. Notice that, when you split the array of keys in half, the two halves have either exactly the same number of keys, or they differ by one. When they have exactly the same number of keys, assigning colors is easy. When they don't, you might need to use some red nodes...