What image format encodes the fastest, or at least faster? PNG is too slow
TL;DR If you want to work in a scene referred workflow you should use OpenEXR. It's also the quickest to save, especially for large renders. I'd recommend to use it with the PIZ lossless codec when rendering in Cycles, since it can compress images with (subtle) noise particularly well.

Let me begin by saying not all image formats are equal, so comparing just the time required for encoding wouldn't necessarily give you a reasonable choice. There are four parameters that are usually of interest when it comes to choosing the right image format for the task:

Bit Depth
Compression
Alpha (Straight vs. Premultiplied)
Encoding Performance

The bit depth is relevant because it determines how much information the image can actually hold, which directly influences the dynamic range your image can have. OpenEXR and Radiance HDR can store 32-bit per pixel in each channel, whereas JPEG has only 8-bit. Naturally if you render the frames you don't want to discard a majority of the information, therefore a higher bit depth is desirable. However storing the raw bits would result in very large file sizes, which is why compression is also relevant.
Compression can be lossless or lossy. The former allows to reconstruct the original values as is. Lossy compression leverages that the human perception doesn't notice slight quality degradation. It can therefore reach higher compression ratios. Whether lossless or lossy compression is faster to store isn't possible to say in general. Using a lossy compression likely results in fewer bytes that have to be written, but the compression algorithm may have a higher computational complexity. This is why the speed of saving the image is also depending on the size of it. PNG, as you noticed, is notoriously slow and has a poor compression ratio. An image format with lossless compression, a high (enough) compression ratio and fast encoding would therefore be preferable. A lossy compression may also be useful if disk space is of the essence and quality loss isn't a concern.
Another area where image formats differ is the alpha. Some image formats don't support it at all and those that do use either unassociated alpha (also called straight alpha) or associated alpha (also called premultiplied alpha). JPEG for instance doesn't have an alpha channel, PNG uses unassociated alpha, OpenEXR associated alpha. While unassociated alpha allows to store occlusion (&quot;transparency&quot;) it cannot model pixels that are simultaneously emissive and semi-transparent which associated alpha can. This is why the latter is suitable for VFX/Compositing and the others are not. For more information see the following answer by Troy Sobotka.
The only image format which is a good solution to all four aspects is OpenEXR. It supports 32-bit depth, good compression (lossless and lossy codecs), associated alpha and good encoding performance. In Blender it also allows you store all your render passes, which is very useful for compositing and a scene referred workflow.

While OpenEXR may be the best choice for the job, is it also one of the fastest solution?
I've written a script which measures the time it takes to store an image in all the image formats Blender offers. Unfortunately Blender's Python API doesn't offer a way to hook into the encoding step, which is why the measurements are for the time required to save the image to disk. Since I/O isn't constant time due to scheduling, the controller, read/write access patterns and usage by other software, the script saves the image(s) multiple times for an average save time as well as the standard deviation to get an impression how strongly the results vary. The following measurements were all made on a Samsung 840 Pro SSD.
Performance comparision with highest quality settings
For the first experiment an HDRI in four resolution is loaded into Blender and saved saved using every image format available. For each format the settings have been set to maximize output quality. The error bar represents the standard deviation.
Remark 2020-06-22: The results may not be representative for every input. Additionally the image formats supporting lossless codecs have the maximum compression ratio set. This increases their encoding time compared to the lossy formats.
All image formats

All image formats except for PNG

The measurement confirms your impression that PNG's performance is pretty terrible at maximum compression. OpenEXR is the fastest out of all the options for the data set it was tested on. Since OpenEXR has also the most desirable properties of all the image formats, it is the best choice. The test use only one codec for OpenEXR though, which is PIZ. Further measurements that compare the available codecs of OpenEXR will give a full picture of the performance.
(Update 2020-06-22) Performance comparision with default compression ratio
Mechalynx criticized the choice of the compression ratio for PNG in the original measurement. Hence, I've repeated the evaluation on the same data, but every image format uses Blender's default compression ratio and quality option. The color channel for the output is set to RGB for every format and the bit depth to the maximum. Note that the maximum supported bit depth varies between formats.

The default amount of compression for PNG is 15% in Blender, which results in greatly reduced saving time compared to the maximum compression in the previous measurement. However, PNG is still among the formats that saves the slowest, even with the default compression settings, for the particular data used in this test.
OpenEXR comparison of codecs
We have established that OpenEXR is one of the best choices among the file formats Blender offers. Next we can take a closer look at the different codecs and which of the lossless and lossy codecs are the fastest.

The lossless PIZ codec seems to be significantly faster on the tested data than the other codecs. It also creates the smallest file size for this particular file at 16500 x 8250 among the lossless codecs with 453.8 MB. DWAA seems to be the fastest among the lossy codecs and it had the smallest file size with 107.2 MB for the 16500 x 8250 image. The last measurement contained a significant outlier for the PXR24 codec which skewed the results.

The script
In case you want to run tests on your own hardware, you can find the script here.
Example for testing on HDRIs
# HDRI can be downloaded from https://hdrihaven.com/hdri/?c=indoor&amp;h=machine_shop_01
filepaths = [
    &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_1k.hdr&quot;,
    &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_2k.hdr&quot;,
    &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_4k.hdr&quot;,
    &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_8k.hdr&quot;,
    &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_16k.hdr&quot;]
file_settings = [BMP(),
                 IRIS(),
                 PNG(),
                 JPEG(),
                 JPEG2000(),
                 TARGA(),
                 TARGARaw(),
                 Cineon(),
                 DPX(),
                 OpenEXRMultilayer(),
                 OpenEXR(),
                 RadianceHDR(),
                 TIFF()]
result_directory = &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding&quot;
benchmark = BenchmarkImage(filepaths, file_settings, result_directory, measurements_per_file=3)
benchmark.run()

Example for testing OpenEXR codecs
# HDRI can be downloaded from https://hdrihaven.com/hdri/?c=indoor&amp;h=machine_shop_01
filepaths = [&quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_1k.hdr&quot;,
             &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_2k.hdr&quot;,
             &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_4k.hdr&quot;,
             &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_8k.hdr&quot;,
             &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding\\hdris\\machine_shop_01_16k.hdr&quot;]
file_settings = [OpenEXR(exr_codec=&quot;DWAA&quot;),
                 OpenEXR(exr_codec=&quot;ZIPS&quot;),
                 OpenEXR(exr_codec=&quot;RLE&quot;),
                 OpenEXR(exr_codec=&quot;PIZ&quot;),
                 OpenEXR(exr_codec=&quot;ZIP&quot;),
                 OpenEXR(exr_codec=&quot;PXR24&quot;),
                 OpenEXR(exr_codec=&quot;NONE&quot;)]
result_directory = &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding&quot;
benchmark = BenchmarkImage(filepaths, file_settings, result_directory, measurements_per_file=3)
benchmark.run()

Example for rendering and measuring the current scene
file_settings = [BMP(),
                 IRIS(),
                 PNG(),
                 JPEG(),
                 JPEG2000(),
                 TARGA(),
                 TARGARaw(),
                 Cineon(),
                 DPX(),
                 OpenEXRMultilayer(),
                 OpenEXR(),
                 RadianceHDR(),
                 TIFF()]
result_directory = &quot;K:\\Bugs_and_Features\\StackExchange\\2019_08_12_performance_encoding&quot;
benchmark = BenchmarkProject(file_settings, result_directory, measurements_per_file=3)
benchmark.run()

For the charts you need matplotlib in Blender. I would recommend to create a venv using the same Python version as Blender uses, install matplotlib in the venv, then create a directory with subdirectories modules, addons, presets and startup. Copy the modules from the venv into the modules directory. Now add the parent directory to Blender's Scripts file path in Edit &gt; Preferences &gt; File Paths and you should be able to import matplotlib.

Update: File size comparison
As suggested by Troy, we can also show that OpenEXR produces significantly smaller file sizes than PNG.

The chart compares the file size of images saved as 16-bit PNG with maximum compression and 16-bit OpenEXR with DWAA (lossy) and PIZ (lossless) codecs.
The file sizes are:
1024x512  :   3.02 MB (PNG),   0.82 MB (OpenEXR - DWAA),   1.70 MB (OpenEXR - PIZ)
2048x1024 :  11.80 MB (PNG),   2.87 MB (OpenEXR - DWAA),   6.52 MB (OpenEXR - PIZ)
4096x2048 :  46.03 MB (PNG),   9.74 MB (OpenEXR - DWAA),  25.23 MB (OpenEXR - PIZ)
8192x4096 : 176.68 MB (PNG),  32.71 MB (OpenEXR - DWAA),  96.13 MB (OpenEXR - PIZ)
16500x8250: 657.86 MB (PNG), 107.19 MB (OpenEXR - DWAA), 352.64 MB (OpenEXR - PIZ)

Evidently OpenEXR also beats PNG in file size, with DWAA creating files that are approximately 72-83% and PIZ 43-46% smaller than the PNG on the tested images.
Although the strong increase in file size makes it hard to read precise values from the chart, they should give a general impression of the required storage. The following one shows the file sizes for all file formats in the same configuration as the timing chart. J2K refused to save the largest resolution, which is why there is no value at 16500 x 8250.


(Update 2020-06-22) OpenEXR vs PNG for baked textures
Since there's been a discussion with Mechalynx in the comments about how well suited OpenEXR is for baked textures, such as normal or displacement maps, I've investigated this as well. One claim was that the original benchmark may not be representative for other types of image content. I've modified the script to evaluate the file size and saving time for baked images. It is also available on GitHub. The following test compares the saving time and required file size for a normal map baked from a high resolution mesh.


In the evaluated data OpenEXR consistently beats PNG in encoding speed. Furthermore, OpenEXR produced smaller files at equal bit depth for all codecs (excluding None which doesn't compress). The lossy codec DWAA produces smaller files than PNG even at 32-bit.
The measurements are just a sample and do not prove that this holds for all or a majority of the input data. Further evaluation on a well designed data set would be necessary to draw a generalized conclusion. However, there is a strong indication that OpenEXR provides better encoding speed and smaller file size compared to PNG when an appropriate codec and comparable bit depth are used.