Of course more k-points take longer time.
For most system (esp. 3D bulk) you can always assume more k-points is more accurate, and a balance needs to be struck between computation time and accuracy, i.e. what is your acceptable level of inaccuracy for a lower k-point sampling than infinite.
Infinite graphene is a bit unusual when it comes to k-point sampling, however, which of course is due to the special Fermi "surface" at the K point.
Consider the following: below I list the top of the valence band and bottom of the conductance band at the K point for k-points up to (41x41).
| Nk VB CB |
| 1 -2.83290807 -2.83266655 |
| 2 -0.09758413 -0.09734262 |
| 3 -0.00012076 0.00012076 |
| 4 0.00443931 0.00468083 |
| 5 0.02010983 0.02035134 |
| 6 -0.49142374 -0.49118223 |
| 7 -0.02140617 -0.02116465 |
| 8 -0.00251439 -0.00227288 |
| 9 -0.00012076 0.00012076 |
| 10 -1.78E-04 6.38E-05 |
| 11 -0.03717076 -0.03692925 |
| 12 -0.00330995 -0.00306843 |
| 13 -0.03310426 -0.03286275 |
| 14 -0.00071831 -0.0004768 |
| 15 -0.00012076 0.00012076 |
| 16 -2.31E-04 1.07E-05 |
| 17 -6.73E-05 1.74E-04 |
| 18 -0.000776 -0.00053449 |
| 19 -0.00167647 -0.00143496 |
| 20 -0.00037827 -0.00013676 |
| 21 -0.00012076 0.00012076 |
| 22 -2.00E-04 4.11E-05 |
| 23 -2.27E-04 1.48E-05 |
| 24 -0.00048527 -0.00024376 |
| 25 -0.00090307 -0.00066156 |
| 26 -2.62E-04 -2.07E-05 |
| 27 -0.00012076 0.00012076 |
| 28 -1.77E-04 6.41E-05 |
| 29 -2.40E-04 1.83E-06 |
| 30 -0.00035275 -0.00011124 |
| 31 -0.00058593 -0.00034442 |
| 32 -2.10E-04 3.17E-05 |
| 33 -0.00012076 0.00012076 |
| 34 -1.62E-04 7.91E-05 |
| 35 -2.26E-04 1.52E-05 |
| 36 -2.82E-04 -4.01E-05 |
| 37 -0.0004267 -0.00018519 |
| 38 -1.82E-04 5.95E-05 |
| 39 -0.00012076 0.00012076 |
| 40 -1.53E-04 8.89E-05 |
| 41 -2.10E-04 3.13E-05 |
This was computed with our Huckel model; since it's a symmetry-related result, the particular method has less of an influence on the conclusions, although in general the Huckel model is just as accurate (if not more, sometimes) for graphene, when using the Cerda basis set. The calculation of all results took 1 minute on my laptop, using the attached script, so there's no excuse for not doing a careful convergence study

Now, if you look carefully, you will find that only for the following k-point samplings (Nk,Nk) will you have the two points straddling the Fermi level symmetrically:
Nk = 3, 9, 15, 21, 27, 33, 39
So, quite simply: 3*an odd integer! Those are the ones you will want for infinite graphene in both 1D and 2D!