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!