They are necessary.. you had them twice in each link, which is why you saw them before.
Use no follow links for any links that you don't wish to give away site value too.. in other words.. when you link to another site, you're giving a little search engine weight to it.. (that's why we teach people to get back links)
But you don't need to give value to affiliate links or pages that don't need to be indexed.. like privacy, contact, terms pages etc...
To make a link no follow replace..
<a rel="nofollow" href=
at the beginning of the link.