This paper presents graph kernel adaptive filters that model nonlinear input-output relationships of streaming graph signals. To this end, we propose centralized and distributed graph kernel recursive least-squares (GKRLS) algorithms utilizing the random Fourier features (RFF) map. Compared with solutions based on the traditional kernel trick, the proposed RFF approach presents two significant advantages. First, it sidesteps the need to maintain a high-dimensional dictionary, whose dimension increases with the number of graph nodes and time, which renders prohibitive computational and storage costs, especially when considering least-squares algorithms involving matrix inverses. Second, the distributed algorithm developed in this paper, referred to here as the graph diffusion kernel recursive least-squares (GDKRLS) algorithm, does not require centralized dictionary training, making it ideal for distributed learning in dynamic environments. To examine the performance of the proposed algorithms, we analyze the mean convergence of the GDKRLS algorithm and conduct numerical experiments. Results confirm the superiority of the proposed RFF-based GKRLS and GDKRLS over their LMS counterparts.