GNUS does several things that take quadratic time of the number of newsgroups that are listed in .newsrc. The quick fix for this is to remove all the newsgroups in which you have no interest from your .newrc file by using GNUS's C-k command in the `*Newsgroup*' buffer after displaying all newsgroups with the L command. If you were to directly edit your .newsrc to remove the newsgroups, GNUS would add them back.
GNUS uses a quadratic algorithm to check for duplicates when the .newsrc file is newer than the .newsrc.el file (ie., you edited your .newsrc). GNUS uses a quadratic algorithm to check for new newsgroups every time it connects to the news server. {There may be other quadratic algorithms that I am not aware of.}
You can speed up GNUS by using the C-k command in the *Newsgroup* buffer to remove newsgroups from your .newsrc file.
Of course, GNUS will run faster if you make sure it is byte-compiled.
Felix Lee wrote some enhancements called `gnus-speedups.el' that fix some of the problems. See the Emacs Lisp Archive.