Como roto una imagen sin que se vuelva borrosa

[CreandoPKMN]

Buenas, estoy usando paint.net, para editar unos sprites, antes he estado usando photoshop pero me pasa el mismo problema, y es que al intentar rotar una imagen, esa imagen se vuelve borrosa, mejor pongo imagenes para que se entienda mejor.
Imagen normal:


Imagen un poco rotada:


Si alguien sabe como resolver eso (si es que se puede), por favor que me lo diga jaja. Venga, gracias y nos vemos.

 

[Gold]

indexalo antes de rotarlo

 

[Ficus]

Depende el programa la opción de mover tiene que decir algo de "Más cercano" y/o "Aproximación"

Adobe Photoshop: Ctrl+T y opción de "Por aproximación"
PaintDotNet: Selección, Mover y opción de "Vecino más cercano"
GIMP: No uso GIMP habitualmente.

EDIT: Acabo de leer que usabas PaintDotNet, es vecino más cercano. Jajajaja

Saludos!