As a PhD Candidate, I've written several successful recommendation letters for students who I've taught in my classes. Is it worthwhile to include this information on a CV, say under "Service"? I've never seen this included before on a CV, but I was hoping there might be a way for me to highlight my contributions to teaching outside of the classroom.
I have not seen this and wouldn't recommend it, I would not consider writing recommendation letters to be under academic "service."
If you specifically mentored particular students then it makes sense to note that mentorship, but if they were just people who took your class then writing them recommendations is just part of your teaching responsibility, it doesn't mean anything for your qualifications if your students were successful when you wrote them recommendations, those are your students' accomplishments rather than yours.
No, you should not list letters of recommendation that you have written on your CV.
It is true that this activity requires time. When you become faculty member, you will write even more letters for students and again you will not list them on your CV. You will also (eventually) write letters of recommendation for graduate students seeking to become faculty, and for faculty peers at other universities seeking tenure or promotions. None of these activities will ever appear on your CV.
Peer review activity that does appear on your CV includes journal, conference, and proposal refereeing activity that you conduct. Of course, you never indicate specifically which works you have refereed.
One more thing: student privacy laws (at least in the US) probably would prevent you from listing student recommendation letters that you have written on your CV, even if it was otherwise a good idea.