Try putting your gnocchi together by cutting all the ingredients together with two bench knives--it's loud, but it's a great way to get out some aggression without overworking the dough.
Don't use them to smear the dough, just to cut straight down through it. I agree with cutting down a bit on the flour and/or using 00 flour.