After much trial-and-error, I found out the problem.
Initially, to find the virtual network of the AKS cluster, I went to the [Kubernetes service] > [azure-prometheus-monitoring(cluster name)]. There, I found the resource group as shown in the image below, and discovered that there is no VNET, hence I went ahead to create one.
I then followed the steps indicated here to do the pairing, but failed. [source:] https://learn.microsoft.com/en-us/azure/aks/private-clusters
Eventually, after much head-scratching, I saw that the Azure Kubernetes page have a properties tab, which has an infrastructure resource group.
If we go to that infrastructure group, I found that there is already an Azure created VNET.
At the Azure created VNET, I added the VNET peering, and voila it worked!.
Note that if you receive the error "cannot be peered because address space of the first virtual network overlaps with address space of virtual network", then you have to go into either of the VNET (i choose the AKS VNET) and change the Address space allocated.
Infrastructure resource group seems to be a crucial part of Azure AKS, but it is almost never mentioned in forum questions and answers, online setup resources, or even official Microsoft Azure "Create a private Azure Kubernetes Service cluster" article. Hence I am answering my own question in the hopes that anyone after me that faces the same problem have some answers. Cheers!