Infrared-faint radio sources (IFRS) form a new class of galaxies characterised by radio flux densities between tenths and tens of mJy and faint or absent infrared counterparts. It has been suggested that these objects are radio-loud active galactic nuclei (AGNs) at significant redshifts (z>2). Whereas the high redshifts of IFRS have been recently confirmed based on spectroscopic data, the evidence for the presence of AGNs in IFRS is mainly indirect. So far, only two AGNs have been unquestionably confirmed in IFRS based on very long baseline interferometry (VLBI) observations. In this work, we test the hypothesis that IFRS contain AGNs in a large sample of sources using VLBI. We observed 57 IFRS with the Very Long Baseline Array (VLBA) down to a detection sensitivity in the sub-mJy regime and detected compact cores in 35 sources. Our VLBA detections increase the number of VLBI-detected IFRS from 2 to 37 and provide strong evidence that most - if not all - IFRS contain AGNs. We find that IFRS have a marginally higher VLBI detection fraction than randomly selected sources with mJy flux densities at arcsec-scales. Moreover, our data provide a positive correlation between compactness - defined as the ratio of milliarcsec- to arcsec-scale flux density - and redshift for IFRS, but suggest a decreasing mean compactness with increasing arcsec-scale radio flux density. Based on these findings, we suggest that IFRS tend to contain young AGNs whose jets have not formed yet or have not expanded, equivalent to very compact objects. We found two IFRS that are resolved into two components. The two components are spatially separated by a few hundred milliarcseconds in both cases. They might be components of one AGN, a binary black hole, or the result of gravitational lensing.